The eight queens puzzle
The eight queens puzzle asks for eight queens on a chessboard with no two attacking each other. The chess composer Max Bezzel published it in 1848, and it has become the classic first example of backtracking search.
A chess puzzle from 1848
Max Bezzel, a German chess composer, posed the puzzle in a Berlin chess journal in 1848. Franz Nauck published all 92 solutions in 1850 and asked the same question for larger boards. Carl Friedrich Gauss followed the puzzle with interest and discussed it in his letters.
One queen per row and column
Eight queens that do not attack each other must stand in eight different rows and eight different columns. So a solution is a shuffle of the numbers 1 to 8, a permutation, with one extra rule: no two queens may share a diagonal. Of the 40,320 permutations, only 92 pass.
Backtracking
Backtracking builds a solution one piece at a time and backs up the moment it hits a dead end. For the queens: place a queen on the first safe square of the next row, and when a row has no safe square, go back to the row above and move that queen on. In 1972 Edsger Dijkstra used the puzzle to explain structured programming with exactly this search.
Symmetry
Turn the board a quarter turn, or reflect it, and a solution stays a solution. That gives up to eight versions of each one. The 92 solutions fall into 12 such families: eleven with 8 members, and one with only 4, because that solution looks the same after a half turn.
The n-queens problem
On an n×n board the question is the same with n queens. There are solutions for every n from 4 up, and their number grows fast: 2 for 4×4, 92 for 8×8, and 14,200 for 12×12. No formula for the count is known; the record values come from large computer searches.
Try it in PictorX
Open Eight Queens and click a square to place a queen; click it again to take it away. Show attacks puts a dot on the squares your queens attack, and queens in red attack each other. Solve runs the backtracking search one step at a time and keeps the queens you placed. Next solution goes through every solution in order, and Size changes the board from 4×4 to 12×12.
Frequently asked questions
Who invented the eight queens puzzle?
Max Bezzel, a German chess composer, in 1848. Franz Nauck published the first full set of solutions in 1850.
How many solutions are there?
92 on the standard board. Counting rotations and reflections as one, there are 12.
Why does the 6×6 board have so few solutions?
It has only 4, all from a single family. The smaller 5×5 board has 10. Larger boards have more and more: 40 on 7×7 and 92 on 8×8.
Does PictorX upload anything?
No. The board is drawn on a canvas in your browser. Save downloads a PNG, and Edit opens that image in the PictorX editor.
Related tools
Eight Queens
Place eight queens on a chessboard so that none attacks another. Try it yourself, watch the backtracking search find a solution step by step, and go through all 92 solutions.
Knight's Tour
Jump a chess knight to every square of the board exactly once. Play it yourself with Warnsdorff hints, or watch Solve finish an open or closed tour. Save the path as a PNG.
The knight's tour
The history and mathematics of the knight's tour: Euler and Warnsdorff, open and closed tours, why odd boards have no closed tour, and how a computer finds one.
Tower of Hanoi
Move a tower of disks across three pegs in your browser. One disk at a time, never a larger disk on a smaller one. The shortest solution is 2ⁿ − 1 moves.
Tower of Hanoi
The Tower of Hanoi: three pegs, one disk at a time, and never a larger disk on a smaller one. The shortest solution is 2ⁿ−1 moves. Édouard Lucas introduced the puzzle in 1883.
Langton's Ant
Run Langton's Ant in your browser. Watch symmetry, chaos and the 104-step highway, then try multi-colour rules, several ants, a hex grid and turmites.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try Eight Queens