The Eight Queens Puzzle: Solutions

How the game works

Tap a safe square to place a queen and tap a queen to take it off. Squares that a queen already attacks are striped, so you can only place a queen where it is safe. If an empty row or column has no safe square left, the board can’t be finished: the game says so, and you undo. Every placing and taking off counts, even the ones you undo, so three stars go to a board placed without second thoughts.

Squares are named as on a chessboard, columns a to h from the left and rows 1 to 8 from the bottom.

One row at a time

Every row needs exactly one queen, and so does every column. That gives a method that always works, called backtracking:

1. Put a queen on the first safe square of the top row.
2. Move down a row and put a queen on its first safe square.
3. If a row has no safe square left, go back up one row, move that queen to its next safe square, and carry on.
4. Repeat until every row has a queen.

It is slow by hand on a big board, but it never misses an answer. A few tricks make it quicker:

• Knight’s moves. Two queens a knight’s move apart never attack each other, and many solutions are made of steps like that.
• Mind the middle. A queen near the middle of the board attacks the most squares, so it leaves the least room for the others.
• Use symmetry. Any solution turned or mirrored is another solution.

Four Queens

There are only two solutions, mirror images of each other: a2, b4, c1, d3 and a3, b1, c4, d2.

Five Queens

Ten solutions, such as a5, b3, c1, d4, e2.

Six Queens

Only four solutions, and none of them touches a corner:

• a3, b6, c2, d5, e1, f4
• a2, b4, c6, d1, e3, f5
• a4, b1, c5, d2, e6, f3
• a5, b3, c1, d6, e4, f2

Seven Queens

Forty solutions, such as a1, b3, c5, d7, e2, f4, g6.

Eight Queens

Ninety-two solutions, or twelve if solutions that are turns or mirror images of each other count as one. Here is one: a8, b2, c4, d1, e7, f5, g3, h6. Read it as a list of columns: the queen in column a is on row 8, in column b on row 2, and so on.

A pattern for many boards

On some boards a simple recipe works without any searching. Go along the columns from a and put the queens on rows 2, 4, 6 and so on, the even rows counting from the bottom, then on rows 1, 3, 5 and so on. On a 4 × 4 board that gives a2, b4, c1, d3; on a 6 × 6 board a2, b4, c6, d1, e3, f5; and on a 7 × 7 board a2, b4, c6, d1, e3, f5, g7. It works whenever the board’s size leaves a remainder of 0, 1, 4 or 5 when divided by six.

The full chessboard is one of the exceptions: on an 8 × 8 board the recipe puts queens on b4 and e1, which share a diagonal. That is why the eight queens puzzle needs real thinking, and why the method of one row at a time is worth learning.

How many solutions there are

The number of solutions jumps around as the board grows:

• 4 × 4: 2 solutions
• 5 × 5: 10
• 6 × 6: 4
• 7 × 7: 40
• 8 × 8: 92
• 9 × 9: 352
• 10 × 10: 724

The 6 × 6 board is the odd one out: it has fewer solutions than the 5 × 5 board, which makes it the hardest of the small boards to finish without backing up.

A Queen in the Corner

With a queen given on a1, four solutions remain. One is a1, b5, c8, d6, e3, f7, g2, h4.

Two Queens Given

With queens given on c5 and g4, exactly one arrangement works: a8, b2, c5, d3, e1, f7, g4, h6. Start with the rows where the given queens leave the fewest safe squares, and the rest falls into place.

A puzzle with a long history

The chess composer Max Bezzel published the puzzle in 1848, and Franz Nauck found all 92 solutions in 1850. Carl Friedrich Gauss was interested in it too. Since then it has become a favourite example for teaching backtracking in computer science, and the same question is asked for boards of every size: every board from 4 × 4 up has at least one solution.