# The N Queens Puzzle

## Seeking The First Solution

The algorithm we use to search for solutions to the ** n Queens on an
n by n chessboard** puzzle 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 captured 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

1 | 1 | ||

1 | 1 | ||

1 | 1 | ||

Q |

We begin with an empty chessboard - for a short but interesting example we'll use
4 by 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 captured by
any other, so it can stay there. However, it *can* capture 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 captured by the Queen on Row 1. Our chessboard now looks like the diagram.

**Number of attempted Queen placements so far:** 1

- Row 1: 1
- Row 2: 0
- Row 3: 0
- Row 4: 0

### Step 2: Placing the Second Queen

1 | 2 | 1 | |

1 | 2 | 1 | 2 |

1 | 1 | Q | |

Q |

We'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 captured 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 captured 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 capture.

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 capture 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 captured 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

- Row 1: 1
- Row 2: 3
- Row 3: 4
- Row 4: 0

### Step 3: Moving the Second Queen

1 | 2 | 1 | |

1 | 1 | 2 | |

1 | 1 | Q | |

Q |

Fortunately, 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 capture. 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

- Row 1: 1
- Row 2: 4
- Row 3: 4
- Row 4: 0

### Step 4: Placing the Third Queen

1 | 2 | 3 | 1 |

1 | Q | 1 | 2 |

1 | 1 | Q | |

Q |

We 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 capture, 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 capture 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

- Row 1: 1
- Row 2: 4
- Row 3: 6
- Row 4: 4

### Step 5: Returning to the First Queen

1 | |||

1 | 1 | ||

1 | 1 | 1 | |

Q |

Looking 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 capture from that Queen in its new position, we now have a brand new pattern of safe squares where the other three Queens can sit.

**Number of attempted Queen placements so far:** 18

- Row 1: 2
- Row 2: 4
- Row 3: 8
- Row 4: 4

### Step 6: Completing the First Solution

3 | 1 | Q | 2 |

Q | 1 | 2 | 1 |

1 | 1 | 1 | Q |

Q |

From 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 by 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

- Row 1: 2
- Row 2: 8
- Row 3: 9
- Row 4: 7

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.