Skip to: Content • End

Lyndenlea

My home on the Web

Seeking the First Solution

The algorithm we use to search for solutions to the n Queens problem is a very simple depth-first search. In basic terms, starting on the bottom row, we place Queens one-by-one on each row of the chessboard, always ensuring that a new Queen can't be attacked by any Queens already on the board. If we manage to fit a Queen on every row, then we've found a solution to the puzzle. But how do we know when we've found the first solution? We simply start with our Queens on the left-hand side of the chessboard.

It is of course possible to begin this algorithm at ANY corner of the chessboard, even to place Queens columns-first rather than rows-first, and still find the same first solution to the puzzle. However, it should be noted that the arrangement of the Queens in the first solution found by such a variation of this algorithm will likely be a mirrored and/or rotated image of "our" first solution. For the sake of consistency, therefore, all solutions on this website will have been found by beginning at the lower-left corner of the chessboard and placing Queens rows-first, exactly as described on this page.

Step 1: Placing the First Queen

Chessboard diagram showing one Queen in square (1,1), with 1's in the squares above that she can attackWe begin with an empty chessboard – for a short but interesting example we'll use 4×4 – and attempt to place our first Queen on the lower-left corner square (or Row 1, Column 1). Now, as it's currently the only Queen on the board it can't be attacked by any other, so it can stay there. However, it can attack a number of other squares so we must next eliminate the squares where a future Queen can't stay.

As we know, a Queen can move either horizontally, vertically, or diagonally. We're only placing one Queen on each Row, so we need only focus on the vertical and the diagonal. So in every square on the chessboard that's either directly above or on a diagonal with our first Queen we put a "1", to denote that the square can be attacked by the Queen on Row 1. Our chessboard now looks like the diagram.

Number of attempted Queen placements so far: 1

Step 2: Placing the Second Queen

Chessboard diagram showing two Queens in squares (1,1) and (2,3), with 2's added to the rows above where the second Queen can attackWe're now ready to attempt to place our second Queen, this time on Row 2. As before, we first attempt to place it in the left-most square on the row, in Column 1. But this square is marked with a "1", meaning it can be attacked by the Queen in Row 1 and we can't stay here. So we simply move our Queen in Row 2 along into Column 2. This, we find, can also be attacked by the Queen in Row 1, so we move along again into Column 3, a square which is unmarked. Our Queen can safely stay here, so once again we need to mark those squares that are now at risk of attack.

Remember that we can ignore the horizontal, because we're only placing one Queen on each Row. We can also ignore any square in the rows below – either vertically or diagonally – because those rows already contain Queens. So it's only the squares either directly or diagonally above our Queen in Row 2 that we need to mark with a "2". However, if a square is already marked as being at risk of attack from another Queen, we can skip it because a future Queen wouldn't want to stay there anyway. The diagram shows our progress so far.

But now we have a problem. Having successfully placed our first two Queens, we would like to place our third Queen on Row 3. But as we try each square in turn, we find that they are all at risk of being attacked by one of the other two Queens. The only solution is to return to our second Queen and see if we can find somewhere else for it to go.

Number of attempted Queen placements so far: 8

Step 3: Moving the Second Queen

Chessboard diagram showing two Queens in squares (1,1) and now (2,4), with 2's again added to the rows above where the second Queen can attackFortunately, the last square on Row 2 is also safe, so we can move our second Queen to here. We now need to reassess which squares in the rows above are at risk of attack. First, we clear all the "2s" we marked back in Step 2. Next, we repeat the marking process with our Queen in its new position in Column 4, as shown on the diagram.

Number of attempted Queen placements so far: 9

Step 4: Placing the Third Queen

Chessboard diagram showing three Queens in squares (1,1), (2,4) and (3,2), now with 3's added to the squares in Row 4 that the third Queen can attackWe can now return to finding a place for our third Queen on Row 3. Trying each square in turn we find a safe place in Column 2, so next we need to mark with a "3" the squares above that are now at risk of attack, as shown on the diagram.

Having successfully placed three Queens, we need only to find a safe place for our fourth Queen in Row 4 and we've found the first solution. Unfortunately, every attempt to place a Queen on Row 4 is unsuccessful, as all four squares are currently at risk of attack by one of the other three Queens. In addition, if we attempt to move the Queen in Row 3 along, we find that each of the remaining two squares is also unsafe. It may seem drastic, but our only choice here is to go right back to Row 1 and move the very first Queen that we placed.

Number of attempted Queen placements so far: 15

Step 5: Returning to the First Queen

Chessboard diagram showing one Queen now in square (1,2), with 1's in the squares above that she can attackLooking at our chessboard diagram now, a lot has happened. Remember that we tried unsuccessfully to move the Queen in Row 3 along into each of the remaining two squares. Then, as the Queen in Row 2 was already at the end of its row, we had no choice but to return to the first Queen that we placed in Row 1 and move it along into Column 2. Marking all the squares now at risk of attack from that Queen in its new position, we now have a brand new pattern of safe squares where the other three Queens might sit.

Number of attempted Queen placements so far: 18

Step 6: Completing the First Solution

Chessboard diagram showing the completed first solution with four Queens in squares (1,2), (2,4), (3,1) and (4,3), with 1's, 2's and 3's in the squares the lower Queens can attackFrom this point, completing the first solution is relatively straightforward. The only free square in Row 2 is in Column 4, so having tried every other square, our second Queen can stay here. This again leaves just one free square in Row 3, so our third Queen can stay in Column 1. And finally, our Queen in Row 4 finds a safe haven at the third attempt, in Column 3. The diagram shows this first solution for the 4×4 chessboard, and the counters below show that we have reached it after attempting to place a Queen a total of 26 times.

Number of attempted Queen placements so far: 26

If we wanted to continue finding solutions, we would simply continue this same algorithm of attempting to placing each Queen until they all fitted. The algorithm would end when the Queen on Row 1 finally exhausted all its squares, at which point we would know we'd found every possible solution.

Only one thing remains now – how do we describe this solution (or indeed, any solution on any size of chessboard) in a brief and consistent manner? This is explained on the next page, Describing Solutions.