Sketch · 2026-07-03
N-Queens, by backtracking.
Place N queens on an N by N board so that none attack another. A depth-first search tries one column at a time, drops a queen in the first safe row, and unwinds every time a column runs out of legal squares. The board below runs that search one step at a time.
How the search moves
The state is a stack of queen positions, one per filled column. Three bitmasks track what the placed queens cover: the rows they occupy, the down-right diagonals, and the down-left diagonals. Each diagonal has a stable index because row + col and row - col are constant along it.
To place a queen in the current column, the search walks down the rows from a cursor. A row is legal only if it is missing from all three masks. When one is found, the queen goes down, the masks pick up its three bits, and the cursor moves to row zero of the next column. When the cursor runs off the bottom, the last queen is removed, its bits leave the masks, and the cursor picks up one row below where that queen stood.
How the numbers grow
On an eight by eight board there are 92 arrangements, split into twelve equivalence classes under the eight symmetries of the square. The count grows fast: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712 for N from 1 to 13. Sequence A000170 in the OEIS. No closed form is known, but the sequence has been enumerated up to N equals 27 by Preusser and Engelhardt, at the cost of several days on an FPGA.
The search tree is much larger than the solution set. On eight by eight, a bare backtracker like this one visits 15 720 nodes to surface those 92 boards. On twelve by twelve, roughly 1.5 million nodes for 14 200 solutions. Turn Find all on to count them; the step counter tracks the exact node budget.
Sources
Max Bezzel posed the eight-queens puzzle in the Berliner Schachzeitung in 1848. Solution counts are OEIS A000170. The record-setting enumeration is Preusser and Engelhardt, Q27: A DLX-based Approach to the N-Queens Problem (2016).