N-Queens

The problem it solves

Place n queens on an n×n chessboard so none attacks another — no shared row, column, or diagonal. Nobody deploys queen placement in production; what N-Queens actually is, is the cleanest possible specimen of a huge problem family: constraint search, where you build a solution piece by piece, and a partial answer can be checked for legality before you’ve committed to the whole. Sudoku solvers, register allocation, scheduling with conflicts, crossword filling, SAT solving — all are this shape, and interviews use N-Queens (and its siblings: subsets, permutations, combination-sum) to test whether you own the shape rather than the puzzle.

The shape’s name is backtracking, and its soul is the step most explanations rush past: not the placing, but the un-placing. A search that can retract its choices can explore an exponential space with only a linear amount of state.

The intuition — and where it breaks down

Threading a maze of decisions, one row at a time. Since two queens can never share a row, every solution has exactly one queen per row — so the search doesn’t wander an n²-square board; it answers n sequential questions: “which column for row 0? for row 1? …” At each row, try a column; if no queen already placed attacks it, place tentatively and descend to the next row. If a row offers no safe column, the truth is brutal and useful: no completion of the current partial placement exists — not “try harder”, but provably empty future. So retract the previous row’s queen and try her next column.

The dead-branch image is the right one: the search walks a tree of partial placements, and a failed row doesn’t kill one candidate — it kills an entire subtree of the exponential space in one stroke, everything that would have grown from the doomed prefix. Pruning early (checking safety at placement, not at completion) is the difference between “clever search” and “enumerate 64-choose-8”.

Where the intuition breaks: people imagine backtracking as retreat, something like failure. It isn’t — the retraction is the algorithm learning: “no solution begins this way” is hard-won information, paid for by the exploration, and the un-placing is how the ledger stays correct. The bug family that defines backtracking — state not restored on the way out — comes precisely from treating the unwind as cleanup rather than as half the algorithm. The visualization counts backtracks as a first-class counter for exactly this reason.

Loading…

A walkthrough you can check

n = 4 — famous for having no solution beginning in column 0.

1. Row 0: place at column 0. Row 1: columns 0, 1 attacked; place at 2. Row 2: every column attacked (0 by both, 1 by c0’s diagonal… walk it — all four fail). Backtrack: retract row 1.
2. Row 1: next option, column 3. Row 2: only column 1 is safe. Row 3: nothing safe. Backtrack, backtrack — row 1 exhausted too. Retract row 0.
3. Row 0: column 1. Row 1: column 3. Row 2: column 0. Row 3: column 2 — safe. Solution: (1, 3, 0, 2).

Count what happened: the doomed column-0 start was fully refuted — every continuation tried and failed — before the search moved on, and that refutation cost a handful of placements, not 4⁴ enumerations. The prompts in the visualization quiz the safety judgment itself (“is this square attacked?”), because the diagonal check — same |row difference| as |column difference| — is the piece people get wrong at the whiteboard.

The invariant

The placed queens are always mutually non-attacking, and every column already retracted at the current row provably leads nowhere given the rows above. The first half means the check happens before placement — the partial solution is never illegal, even momentarily. The second half is why termination with an empty row 0 means “no solution exists” rather than “didn’t find one”.

The state invariant is the engineering half: after place(row) returns — success or failure — the board is exactly as it was before the call. Every mutation (the queen, the attack sets) is undone on the way out. That in-and-out symmetry is the entire discipline of backtracking, it’s what lets one shared board serve an exponential search, and its violation is the defining bug of the genre: a stray queen from a failed branch silently poisoning every sibling branch’s safety checks.

Complexity, derived

The search tree has at most n choices per row over n rows — O(n^n) naive, tightened to O(n!) by the column constraint (each row has fewer free columns than the last), and slashed far below that in practice by diagonal pruning: the n=8 board finds its first solution after a few hundred placements, not 8! = 40,320. No polynomial bound exists — counting solutions is genuinely hard, and the count (92 for n=8; no closed formula known) is itself a famous open-ended fact. Space is the beautiful part: O(n) — the current column list and attack sets — for a search over an exponential space. The recursion depth is n, full stop.

The attack check is where implementations separate: scanning all placed queens per square is O(n) per check; three boolean sets — columns, diagonals indexed by row+col, anti-diagonals by row−col — make it O(1), and those two index formulas (constant along each diagonal direction — check it on paper) are the trick worth memorizing. Bitmask versions pack the three sets into integers and shift them per row; that’s the competitive-programming form, and the reference solver in this repo’s tests uses it.

What people get wrong

Not undoing state after the recursive call. The genre-defining bug, worth naming twice. Symptoms: solutions missed, or phantom “attacks” from queens no longer on the board. The fix is structural — mutate, recurse, unmutate, in that order, with nothing able to skip the third step.

Checking rows. One queen per row is guaranteed by construction — the recursion places exactly one per row. Row checks are dead code that signals the structure wasn’t understood.

Getting the diagonal formulas wrong. row+col constant on one direction, row−col on the other. Swapping or misremembering them passes small boards by luck and fails at n=6.

Returning the first solution when all were wanted (or vice versa). “Find one” returns on success; “count/collect all” records and continues — and the continue path must still unwind state. The two variants differ by one early-return, and mixing their skeletons produces double-counted or missing solutions.

Half-hearted pruning. Checking legality only at the bottom of the tree (“place all n, then validate”) is technically backtracking and practically enumeration — the exponential savings live entirely in pruning at placement time.

Implementation notes across languages

Python: three set()s for columns/diagonals, add/remove around the recursive call — readable and fast enough through n≈12; the bitmask form (cols, diag1<<1, diag2>>1 per row) is the speed ceiling and a classic elegant snippet. Java/C++: boolean arrays beat hash sets (indices are small integers: 2n−1 diagonals); C++ competitive solutions do n=15 with bitmasks in milliseconds. JavaScript: numbers are 32-bit for bitwise ops — the bitmask trick works up to n=32, plenty. Across languages, the transferable move is recognizing the skeleton elsewhere: subsets (choose/skip per element), permutations (choose per position from remaining), sudoku (N-Queens with 3 constraint sets per cell) — same choose-recurse-unchoose, same one invariant, same one bug to not write.