Here is my solution.
(I only need to find 1 such solution i.e only 1 placement of queen. Not all possible solutions-92)
Place a queen on board when there is no conflict with the other queen(diagonalwise, row-wise, col-wise)
Do this till you reach the last column.
If there is conflict, reset and start again.
when is N-queens said to be solved? (I need to figure out just 1 solution)
N-queens is said to be solved when you've reached the last column and there's no conflict till now.
According to Wikipedia, the eight-queen problem has 92 solutions (although it is unclear whether this includes reflections and rotations). The four-queen problem must have millions of solutions.
Just placing four queens on random different squares has 64 x 63 x 62 x 61 possibilities (i.e. 15,249,024), before you even consider whether any two from four share a row, column or diagonal.
Placing eight queens on random different squares has 178,462,987,637,760 possibilities. So eliminating the conflicts as early as possible is crucial. For example, if the first Q is at (1,1), the second Q cannot be placed any closer than (2,3).
4 queen problems mean 4*4 board and 4 queens
Excuse my ignorance. I got lucky -- my first intuitive try of 4*4 by hand is a solution.
(Hint: Once a Queen, always a Queen. Once a Knight is enough.)
I don't know how to count rotations and reflections. If the Queens all wear the same crowns, I think there are only two solutions -- rotations are identical, and reflections are the same vertically and horizontally. If the Queens have different crowns, I think there are 3 * 2 extra solutions (because some coincide with rotations), so 12 solutions in all.
I suspect you need to be more specific about placements to optimise this at all. Random placements will take forever (because you are not eliminating possibilities, and because you may repeat yourself).
If you place the first queen in a specific sequence like 1,1 1,2 ... 1,8 2,1 ... , then there is no point placing the second queen anywhere the first queen has already been placed, because all queens look the same.
You can also make an initial mapping of which positions are eliminated by a placement attempt. For example, Q at 2,3 eliminates 2,3 plus 7 places in row 2, 7 more in column 3, and 7 more in the two diagonals. So when you place the next queen, you can skip ahead for the marked columns, instead of checking each queen against all the previous ones.
I have not worked out how this works in practice. However, I wrote a Sudoku code (both to solve and to invent new boards) using similar concepts. It works for many configurations, including the usual 9x9 and the Samurai (21x21 made up of five overlapping 9x9s). It is in awk, and solves about 5 problems a second.
As I understand the 4 queens puzzle, there are only 2 solutions.
See:
See also:
//Solves 4 queen using nested for loops.
public class FourQueen {
public static int NO_OF_QUEENS = 4;
public static void main(String[] args) {
int [] board = {-1, -1, -1, -1};
for (int i = 0; i < NO_OF_QUEENS; i++) {
board[0] = i;
for (int j = 0; j < NO_OF_QUEENS; j++) {
board[1] = j;
if (noKill(board, 1)) {
for (int k = 0; k < NO_OF_QUEENS; k++) {
board[2] = k;
if (noKill(board, 2)) {
for (int l = 0; l < NO_OF_QUEENS; l++) {
board[3] = l;
if (noKill(board, 3)) {
displayQueens(board);
}
}
}
}
}
}
}
}
private static void displayQueens(int[] board) {
System.out.println("-------------");
int n = board.length;
for (int row = 0; row < n; row++) {
System.out.println("Hello");
for (int value : board) {
if (value == row) {
System.out.print("Q\t");
} else {
System.out.print("*\t");
}
}
System.out.println();
}
}
private static boolean noKill(int[] board, int currentColumnOfQueen) {
for (int i = 0; i < currentColumnOfQueen; i++) {
// same row
if (board[i] == board[currentColumnOfQueen])
return false;
//Diagonal
if ((currentColumnOfQueen - i) == Math.abs(board[currentColumnOfQueen] - board[i])) {
return false;
}
}
return true;
}
}
I'm not interested in its code solution which is available everywhere. I am trying to formulate code based on logic. It's not my homework to solve quickly.
Agreed there is one fundamental final solution. The second solution can be reached via one reflection (either horizontal or vertical).
Interestingly, as I hinted, there are possible two Knight's Tours (if you ignore rotations and reflections), and one of those is identical to the four Queens solution.
If you regard the Queens as distinct beings, then there are additional countable ways that a sequential algorithm might order placement of the Queens (which would include rotations). But those are not final solutions -- just interim states.
If you read the reference I posted, they go though the complete logic they use to solve this puzzle.
You don't have to use their code, but surely you can read references and learn from others!
How you wish to code it, is up to you 
I have a detailed logic that seems to offer an efficient approach to solving this problem. I don't have any code written for it.
It seems simple to design a way of constructing the 4x4 board that avoids having to check for row-wise and column-wise conflict. It does that simply by not generating those cases.
Consider a 4x4 grid from (1,1) to (4,4). A one-dimensional vector can describe that whole 2-D grid. For example (4,1,3,2) uniquely describes this grid.
.Q..
...Q
..Q.
Q...
where the first number 4 says the first column has a Queen on row 4, etc.
If the values in the vector are any permutation of (1,2,3,4), then each row, and each column, can only contain one Q. So no row or column conflicts can occur. For a 4x4 grid, there are only 24 (4!) possible grids. For an 8x8 grid, there are only 40320 (8!) possible grids. Generating a complete sequence of permutations is a simple recursive algorithm.
All that remains is to check diagonals. The conflict between two Queens is symmetrical: if Qa checks Qb, Qb checks Qa. So we can order the checking to avoid duplication.
If we check for conflicts column by column from the left, we only need to check the left-down and left-up diagonals. The first column cannot have any conflicts with itself. Column 2 only needs to check conflicts with column 1. We can abort on the first conflict, so that is a useful optimisation. Each Q only has to check two left-diagonals, up to the grid boundaries (left, top or bottom).
In the grid above, column 2 Q checks (r2,c1), Q3 checks (r2,c2) (r4,C2) and (r1,c1), Q4 checks (r1,c3) and conflicts with (r3,c3).
Can anybody see a flaw in that logic?
https://liveexample.pearsoncmg.com/html/EightQueens.html
Found another good code, but yet having hard time with framing it w/o copy pasting.
I followed up my logic outline posted yesterday, and got something that works. It is about 80 lines of code (actually, 65 lines of gawk and 12 lines of Bash wrapper), including a lot of Debug, and a few comments.
It finds the 92 eight-queens solutions in 1.2 seconds, and the 352 nine-queens solutions in 11 seconds. I rely on single-digits strings for the permutations that construct the boards, but I could fix that with some simple tokenisation and do larger boards.
Happy to show code, but maybe not until others get a shot.
Hi @Paul_Pedant,
your idea is clever, but it is already mentioned in the wiki article, under Constructing and counting.
The solution How to solve the 4 queens puzzle in Java is not only far too complicated, but especially static for only 4 queens. In addition, it is solved with 4 nested loops, which is quite ugly.
The Python program given at the end of the wiki article is most probably the fastest and most elegant solution, but it is only a modified version from legendary Niklaus Wirth's solution. And it is not easy to understand.
Here is an even shorter Python version based on the permutation approach. It is correct, but has the Big O notation ~O(n^n), which becomes veeery slow from about n=10. It is therefore practically only useful for n<10
import itertools
for p in itertools.permutations(range(N)):
if all(abs(p[j]-p[i]) != j-i for (i, j) in [(i, j) for i in range(N-1) for j in range(i+1, N)]):
print(p)
It checks the diagonal conflicts by ensuring that for a valid permutation ((0, p_0), (1, p_1), ...) = ((col_0, row_0), ...)) abs(p_i-p_j) != j-i must hold, i.e. abs(row_i-row_j) != col_j-col_i for all 0 <= i,j < n and j>i. In other words, if e.g. abs(row_0-row_2) == col_2-col_0, means that the two queens stand on (0,0) and (2,2) or on (0,2) and (2,0).
My Big-O (bless you, Roy Orbison) seems to be O( n !), which given the number of cases grows like that, suggests my time per board is largely unaffected by board size.
I suspect that is because my diagonal check seldom needs to go very far. It only needs to check previous columns (go-left strategy), and it works its way out from the new Queen on both diagonals simultaneously. I don't even create the board array (except for debug). My conflict check just considers where another Queen would have been if I had made the 2-D representation.
I was checking all conflicts to be sure the algorithm was sound, and when I switched to stop on first conflict I got something around a x4 performance too. I'm not really one for optimising things that run in 10 seconds.
I'm planning to fix my 1..9 string permutation to use A..Z, and then convert to 1..26 to get bigger boards. I didn't fancy writing a generator function in awk, so I just put the perms in an array up front. I expect to run out of time, memory and enthusiasm simultaneously.
It is quite difficult to make an original discovery about a problem that was first stated in 1848. But I did at least discover that optimisation independently --I only looked for the Wiki article when I wanted to verify the number of solutions for the other board sizes.
I note the front-page symmetrical solution on the Wiki consists of two short Knight tour sequences, so my previous "Once a Knight" spoof comment seems to hold up well. I'm wondering if there is another optimisation lurking there.
My usual technique for intractable tasks is to come up with a brute-force approach (regardless of lifetime-of-universe constraints, but it can clarify the problem nicely). Then find some off-the-wall optimisation. And then find another one.
Here, my two insights both came from drawing the 4x4: the first from planning how to generate all 24 or 40320 test cases (I was never going to be satisfied with the small problem), and the second when drawing in the diagonals by hand on a 4x4, and noticing some conflicts were already part-drawn. I feel the need to do some statistics on how many columns get checked before finding the first conflict (this is the first problem I recall with literal corner-cases).
I once got three optimisations in a row. Some colleagues on a client site had a script that was set to run for 30 days -- it ran from Thursday night to Tuesday morning before they found it was unkillable, and when I managed to slay it for them, we found from the truncated results that it was only 15% through.
I managed to get it down to predicted 2 days (optimise the repeated decompress of 800 database logs), then 2 hours (one-time extract of required rows and columns only), then 2 minutes (use nawk to avoid a bug in Solaris fgrep).
EDIT: I did the stats on how helpful it is to check conflicts only to the left, instead of a four-way check on each Queen. They are far better than I expected. On the 8x8 board, these are the percentages eliminated by the left-diagonal check at each column.
Col 2: 25%
Col 3: 33%
Col 4: 21%
Col 5: 12%
Col 6: 6%
Col 7: 2%
Col 8: 1%
Valid: 0.228%
The solution by @munkeHoller jarred a bone somewhere in my head, which led me to a two-time performance lift.
In my notation, this would be a "84136275" solution. The initial "8" signifies that the Queen in column 1 is in row 8, "4" marks column 2 row 4, etc.
Reflections and rotations mean that there are several Variants (possible ways to lay out any solution) for each unique Base Case. I generate my test cases as permutations of the required number of digits, so they are in ascending numeric order.
As one of the reflections is the vertical flip, any test case where the Queen placed in column 1 is in the bottom half of the board, must have another variant where she is in the top half (for an odd board size like 7, rows 1-4 are the top "half").
Therefore, my algorithm will first encounter each solution with the lowest number as the base case. For example, this 84136275 solution must be a variant of the 15863724 base case. For an 8x8 board, there is no need to check rows 5-8. Thus, the run time is halved. My 8x8 test now completes with real 0m0.630s, of which generating the permutations takes about a third of the time.
On a personal note…
I’m not particularly interested in having a human create algorithms and code for the 4-queens problem. That’s something we can each do using our unique human reasoning and coding skills.
Instead, I’ve been working with the latest version of ChatGPT (4o), which, as an LLM, lacks reasoning abilities. My goal was to get ChatGPT to generate an array (set or hash) of 16 arrays representing the queen at every position on a 4x4 board. Essentially, I wanted ChatGPT to generate the correct set of 16 arrays for all possible queen positions.
After spending some time on this, I have not been able to find instructions that would enable this generative AI to produce those 16 arrays correctly.
I started by scaling down to a 2x2 board, which ChatGPT handled easily, generating the 4 arrays without issue.
Next, I tried a 3x3 board. ChatGPT initially struggled, but with some guidance, it was eventually able to generate the 9 arrays correctly.
However, when I moved to a 4x4 board, regardless of how I explained the problem, ChatGPT could not generate the required 16 arrays correctly.
In my discussions with ChatGPT, we reflected on the differences between human reasoning and our ability to visualize problems. Since ChatGPT lacks both reasoning and visualization, it could not accurately generate the 16 arrays after hours of collaboration.
Interestingly, ChatGPT could generate code to solve the 4x4 problem since there are many examples of this online within its LLM training. But because I specifically asked it to generate the “queen’s move arrays” for each of the 16 positions (instead of writing code to solve the problem), we were unable to break through to the correct solution.
My real task was to map my easy human visualization of the 16 positions into instructions that a generative AI could follow to generate the arrays. So far, I haven’t been successful.
ChatGPT and I concluded that humans, with our ability to visualize, find problems like this easy to solve. We can come up with algorithms because we “see” the solution. LLMs, however, lack visualization and reasoning skills, so they can’t generate answers like this unless those answers already exist in their training data.
While I feel like I’ve failed in this particular task, I still believe there’s a way to instruct a generative AI like ChatGPT to generate the 16 arrays—though I haven’t found it yet.
To me, once the arrays are in place, solving the problem logically is straightforward. Of course, I could manually create the arrays and write the code to solve it myself. But what I’m really interested in is getting ChatGPT 4o to generate the arrays and place them in an array or hash. Solving the problem isn’t as interesting as getting ChatGPT to correctly generate the arrays (from my perspective).
Done!
After dinner, I simply asked ChatGPT to generate the positional arrays using a backtracking algorithm, and it had some python code in it's training data.
Here are the 16 positional arrays representing the queen’s movements for each position on the 4x4 board: Position 0 (Top-Left Corner): [1, 1, 1, 1] [1, 1, 0, 0] [1, 0, 1, 0] [1, 0, 0, 1] Position 1 (Top-Middle Left): [1, 1, 1, 1] [1, 1, 1, 0] [0, 1, 0, 1] [0, 1, 0, 0] Position 2 (Top-Middle Right): [1, 1, 1, 1] [0, 1, 1, 1] [1, 0, 1, 0] [0, 0, 1, 0] Position 3 (Top-Right Corner): [1, 1, 1, 1] [0, 0, 1, 1] [0, 1, 0, 1] [1, 0, 0, 1] Position 4 (Middle-Left): [1, 1, 0, 0] [1, 1, 1, 1] [1, 1, 0, 0] [1, 0, 1, 0] Position 5 (Center Left): [1, 1, 1, 0] [1, 1, 1, 1] [1, 1, 1, 0] [0, 1, 0, 1] Position 6 (Center Right): [0, 1, 1, 1] [1, 1, 1, 1] [0, 1, 1, 1] [1, 0, 1, 0] Position 7 (Middle-Right): [0, 0, 1, 1] [1, 1, 1, 1] [0, 0, 1, 1] [0, 1, 0, 1] Position 8 (Bottom-Left Corner): [1, 0, 1, 0] [1, 1, 0, 0] [1, 1, 1, 1] [1, 1, 0, 0] Position 9 (Bottom-Middle Left): [0, 1, 0, 1] [1, 1, 1, 0] [1, 1, 1, 1] [1, 1, 1, 0] Position 10 (Bottom-Middle Right): [1, 0, 1, 0] [0, 1, 1, 1] [1, 1, 1, 1] [0, 1, 1, 1] Position 11 (Bottom-Right Corner): [0, 1, 0, 1] [0, 0, 1, 1] [1, 1, 1, 1] [0, 0, 1, 1] Position 12 (Bottom-Left Corner): [1, 0, 0, 1] [1, 0, 1, 0] [1, 1, 0, 0] [1, 1, 1, 1] Position 13 (Center Left): [0, 1, 0, 0] [0, 1, 0, 1] [1, 1, 1, 0] [1, 1, 1, 1] Position 14 (Center Right): [0, 0, 1, 0] [1, 0, 1, 0] [0, 1, 1, 1] [1, 1, 1, 1] Position 15 (Bottom-Right Corner): [1, 0, 0, 1] [0, 1, 0, 1] [0, 0, 1, 1] [1, 1, 1, 1] These arrays show all possible moves for a queen at each position on the 4x4 board. Let me know if this aligns with your expectations! 
Seems OK af first glance. Here is the same data as a hash of 1D arrays:
queen_moves_1d = {
'Position 0' => [1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1],
'Position 1' => [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0],
'Position 2' => [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0],
'Position 3' => [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1],
'Position 4' => [1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0],
'Position 5' => [1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1],
'Position 6' => [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
'Position 7' => [0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1],
'Position 8' => [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0],
'Position 9' => [0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0],
'Position 10' => [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
'Position 11' => [0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1],
'Position 12' => [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1],
'Position 13' => [0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1],
'Position 14' => [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
'Position 15' => [1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1]
}
Need to confirm, but I think these arrays may be correct, looking at it visually. Need more time later to check.
I must say you're obsessed with chatgpt. Haha. Do you've chatgpt plus? If yes, I get you. Else chatgpt is pretty much stupid like first time learner.