N-queens backtracking

Pick a board size and a method and press Play. In backtracking the board shows the queens placed so far, shades every square they attack, and marks the square being tried. The counters on the right count every placement, skip and backtrack.

• On 8 queens, step through the first solution. Notice how often a row turns out to have no safe square, and the search unwinds.
• Switch to all solutions and run to the end: every one of the 92 solutions is found by the same procedure, carried on after each success.
• Try min-conflicts on 12 queens: all queens start on the board and a handful of moves repair it.

The search code is checked against the known solution counts (OEIS A000170) for boards of 1 to 14, and every solution it reports is verified.

The N-queens problem asks for a way to place N chess queens on an N × N board so that no two share a row, a column or a diagonal. Since every row must hold exactly one queen, a solution is a list of N column numbers, one per row, with no column repeated and no two queens on a diagonal. Solutions exist for every N except 2 and 3.

It is a standard example of a constraint satisfaction problem and the usual first exercise in backtracking search.

Backtracking builds a solution one decision at a time and abandons a partial solution as soon as it cannot be completed. For N-queens:

1. In the current row, take the leftmost column not attacked by any queen above.
2. If there is one, place a queen and move to the next row; if all N rows are filled, record a solution.
3. If there is none, go back to the previous row, remove its queen and try its next column.

Checking whether a square is attacked is constant time with three arrays of flags: used columns, used diagonals (row + column) and used anti-diagonals (row − column). Fast implementations keep the same information in three bitmasks and find all safe columns of a row with a few bitwise operations.

Queens placed by backtracking (the nodes of its search tree), compared with the N^N arrangements a search without pruning would examine:

Steven Minton and colleagues showed in 1992 that for finding a single solution, repairing a complete assignment beats building one. Place a queen in every row, for instance greedily so that each takes the least-attacked square given the rows above, then repeatedly pick a queen that is attacked and move it within its row to the square attacked by the fewest queens, breaking ties at random. Average moves to a solution in this simulator, over several runs:

The same pattern of choose, check, recurse and undo solves Sudoku, graph colouring, subset sum, generating permutations and combinations, and parsing with regular expression engines that backtrack. SAT solvers are backtracking search with far stronger pruning: they propagate the consequences of each choice and learn new constraints from every dead end, which lets them handle problems with millions of variables.

The chess composer Max Bezzel published the eight queens puzzle in 1848, and Franz Nauck gave the first solutions in 1850 and generalized it to N queens; Carl Friedrich Gauss also worked on it. In computing, Niklaus Wirth used it to illustrate "Program development by stepwise refinement" in 1971, and Edsger Dijkstra used it in 1972 to illustrate structured programming with a depth-first backtracking algorithm. Minton, Johnston, Philips and Laird published min-conflicts in 1990 and in the journal Artificial Intelligence in 1992.