N-Queens: How Backtracking Prunes an Exponential Search

A deceptively small board

Place N queens on an N×N chessboard so that no two share a row, column, or diagonal. For N=8 the naive approach — try every way to place 8 queens among 64 squares — is C(64,8), over 4 billion combinations. Restricting to one queen per row and per column (a queen attacks along both, so no valid solution can repeat either) cuts that to 8! = 40,320 permutations, but you still have to check every one for diagonal conflicts unless you search smarter.

Backtracking: build, check, undo

Backtracking places queens one row at a time and abandons a partial placement the instant it becomes impossible to extend — long before all N queens are down. That is the entire idea: incremental construction plus early rejection, which turns an exponential brute-force search into something that finishes for N=8 in a fraction of a millisecond.

function solve(row, cols, diag1, diag2):
    if row == N: record solution; return
    for col in 0..N-1:
        d1 = row - col + N        // "/" diagonal id
        d2 = row + col            // "\" diagonal id
        if col in cols or d1 in diag1 or d2 in diag2:
            continue               // conflict — skip, don't even recurse
        place queen at (row, col)
        solve(row + 1, cols ∪ {col}, diag1 ∪ {d1}, diag2 ∪ {d2})
        remove queen at (row, col)   // ← the "backtrack" step

Each of the two diagonal directions is tracked with a single integer id per diagonal — cells on the same "/" diagonal share row+col, cells on the same "\" diagonal share row-col — so a conflict check is three set lookups, O(1) each, rather than scanning already-placed queens. That single change is why a naive recursive placement without these id sets is noticeably slower than the version shown here, even though both are technically backtracking.

How much pruning actually happens

The search tree for placing N queens one row at a time has, in principle, N^N leaves if you ignore all constraints. Column and diagonal pruning collapses that enormously: N=8 has 92 solutions (12 up to symmetry) reachable after visiting only a few thousand partial placements, and even N=20 — with 39×10^15 raw permutation orderings if you only restrict by column — solves in well under a second with row-by-row backtracking, because almost every branch dies within the first few rows. The number of solutions itself grows roughly like a constant to the Nth power (empirically around 2.5 to 2.7 per additional queen for the range that has been computed exactly), but nobody has proved a closed-form formula — solution counts beyond N≈27 are known only from dedicated large-scale search efforts, not derivation.

Why it stands in for a much bigger class of problems

N-Queens is the textbook example of a constraint satisfaction problem (CSP): variables (one per row), domains (which column), and constraints (no shared column or diagonal). The same backtracking-plus-pruning skeleton, with the constraint-checking logic swapped out, solves Sudoku, graph colouring, exam timetabling and circuit layout. Two general-purpose CSP accelerations map directly onto N-Queens: constraint propagation (forward checking — after placing a queen, immediately shrink the candidate columns for future rows instead of waiting to discover a conflict later) and variable ordering heuristics like minimum-remaining-values (place the most constrained row next), both of which prune the tree earlier and can turn an already-fast search into a dramatically faster one on harder CSP instances even when they barely matter for plain N-Queens.

Beyond backtracking

For very large N, local search beats systematic backtracking: start with all N queens placed (one per row and column, conflicts allowed) and repeatedly move the queen with the most conflicts to the column that minimises conflicts — a form of hill climbing called min-conflicts. It solves boards of a million queens in roughly linear time, a striking contrast to backtracking's exponential worst case, precisely because it never has to construct a solution incrementally from an empty board; it repairs an already-complete-but-flawed one.

Frequently asked questions

Try it live

Everything above runs in your browser — open N-Queens and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.