Backtracking

The 10-second versionCopy Anchor Link

Backtracking solves a problem by building a solution incrementally, one choice at a time, and abandoning a partial solution the moment it becomes impossible. The rhythm is always the same three beats: choose a value, explore by recursing, then un-choose to restore the state and try the next value. It's brute force with a conscience — instead of enumerating all 2ⁿ or n! possibilities and testing each, you prune whole subtrees the instant a partial answer can't be completed. It doesn't make the worst case fast; it makes the typical case vastly smaller than the worst case, which is usually what you need.

Why this existedCopy Anchor Link

Backtracking grew out of puzzles, and its most famous puzzle predates the computer by a century. The problem: place n queens on an n × n chessboard so that no two attack each other — same row, same column, or same diagonal, all forbidden.

• 1848 — the chess writer Max Bezzel poses the eight queens problem.
• 1850 — Franz Nauck generalizes it to n queens and, notably, publishes a method that builds a solution row by row and backs up on failure — an algorithm, on paper, before there was a machine to run it. Gauss himself took an interest.
• 1950s — D. H. Lehmer, working on combinatorial puzzle-solving, names and popularizes the technique "backtracking." The name stuck because it describes the mechanism exactly: when you hit a dead end, you back up.
• 1960 — Martin Davis and Hilary Putnam apply backtracking-style search to Boolean satisfiability (SAT), launching decades of solvers.
• 2000 — Donald Knuth publishes Dancing Links (DLX), a data-structure trick that makes backtracking over "exact cover" puzzles (Sudoku, n-queens, polyominoes) brutally fast — and the whole point is doing and undoing a choice in constant time.

Why it mattered then: by the 1950s, people wanted to solve real combinatorial problems — scheduling, routing, circuit design — and the honest brute force ("try everything") was hopeless. Backtracking was the first general technique that said: you don't have to finish a wrong guess to know it's wrong. Detect it early, back up, move on.

Inside the inventor's headCopy Anchor Link

Picture the eight-queens problem on paper. The naive plan is obvious and terrible: you could try every way to place eight queens on sixty-four squares — that's C(64, 8), about 4.4 billion combinations — and check each one.

Even the natural refinement, "one queen per row," still has 8⁸ = 16.7 million placements, and "one per row and column" is 8! = 40,320 permutations. Each step down is progress, but all three share the same flaw: they place everything first and check for attacks last. Watch how silly that is:

The pivot is the question the inventor finally asks: why finish a doomed placement? The moment you place a queen that shares a column or diagonal with one already down, nothing you do below can fix it. The conflict is permanent. So rip it out immediately and try the next column. That's the aha — validate as you go, not at the end.

This is "choose → explore → un-choose" in its purest form. Here is the naive all-at-the-end checker versus the incremental one:

// Naive: fill every row, only check the FULL board at the end.function checkAll(q) {  for (let i = 0; i < q.length; i++)    for (let j = i + 1; j < q.length; j++)      if (q[i] === q[j] || Math.abs(q[i] - q[j]) === j - i) return false;  return true;   // checked only after committing to everything}// Pruned: is column c safe in `row`, given queens already placed in rows 0..row-1?function safe(q, row, c) {  for (let r = 0; r < row; r++)    if (q[r] === c || Math.abs(q[r] - c) === row - r) return false;  // col or diagonal  return true;    // checked BEFORE going deeper -- no doomed subtree is ever entered}

The final approachCopy Anchor Link

The universal shapeCopy Anchor Link

Every backtracking algorithm is the same skeleton. Learn it once:

Those five words — the loop, the prune test, choose, explore, un-choose — are the whole technique.

The search tree, and where the pruning bitesCopy Anchor Link

You can picture the entire process as a tree: each level is a decision, each edge is a choice, each leaf is a complete candidate. Backtracking is a depth-first walk of that tree — and pruning means not visiting whole subtrees. For 4-queens:

Under c0, the r1 c0 and r1 c1 subtrees are cut before they cost you a single deeper step. On a real 8-queens board this is the difference between exploring millions of leaf placements and a few thousand — the pruned tree has around 2,057 nodes total.

If you've read Depth-First Search, this should feel familiar, because it is DFS: the graph is the space of partial solutions, and the recursion's call stack holds exactly the path from the root to the current node. Backtracking is DFS plus the discipline of restoring state on the way back up.

The invariantsCopy Anchor Link

Two invariants keep it correct, and both are about undoing:

• Validity invariant — at every node, the partial state is a valid partial solution: no two immaterial constraints violated. This is guaranteed because we prune before we descend, so we never enter a state we already know is broken.
• Restoration invariant — when backtrack returns, the state is byte-for-byte what it was on entry. Every mutation is paired with its inverse, so the loop's next candidate starts from a clean slate. Get this wrong (forget one undo) and you'll chase ghosts: solutions that don't exist, or valid ones you never reach.

A worked traceCopy Anchor Link

Solve 4-queens. Recursion places one queen per row; q = [?, ?, ?, ?] holds the column of each row's queen.

• Row 0: try c0 → valid. q = [0, …].
• Row 1: c0 shares the column (prune), c1 shares a diagonal (prune), c2 valid. q = [0, 2, …].
• Row 2: c0 valid. q = [0, 2, 0, …].
• Row 3: c0 col-clash, c1 diag-clash, c2 col-clash, c3 diag-clash — all pruned. Dead end. Back up: undo row 2, then row 1.
• Row 2 next candidate c1: diagonal clash with row 1's c2? |2 − 1| = 1 = 2 − 1, yes clash → prune; c2 col-clash; c3 col-clash. Dead end. Back up to row 1.
• …continue. Eventually q = [1, 3, 0, 2] completes: a solution. Record it, back up, and keep going — the second solution is [2, 0, 3, 1].

The full implementationCopy Anchor Link

function nQueens(n) {  let count = 0;  const col = new Array(n).fill(false);  const d1 = new Array(2 * n).fill(false);       // row + col  const d2 = new Array(2 * n).fill(false);       // row - col + n  const solve = (row) => {    if (row === n) { count++; return; }          // complete solution    for (let c = 0; c < n; c++) {      if (col[c] || d1[row + c] || d2[row - c + n]) continue;  // PRUNE      col[c] = d1[row + c] = d2[row - c + n] = true;           // CHOOSE      solve(row + 1);                                          // EXPLORE      col[c] = d1[row + c] = d2[row - c + n] = false;          // UN-CHOOSE    }  };  solve(0);  return count;}

ComplexityCopy Anchor Link

The honest headline: backtracking does not improve the worst case. What it improves is everything else — the constant factors and the number of nodes actually visited on real inputs. When the search space is huge but constrained, that's the whole game.

Where you meet it todayCopy Anchor Link

• Sudoku and puzzle solvers. Every Sudoku engine is backtracking over the empty cells, pruning the instant a row, column, or box is violated.
• SAT / SMT / constraint solvers. Z3, MiniSat, and OR-Tools run industrial-strength backtracking (plus unit propagation and clause learning) to schedule shifts, verify hardware, and solve NP-hard planning.
• Regular-expression engines. Backtracking regex engines (the default in most languages) explore alternatives depth-first — which is exactly why a badly written pattern can "catastrophically backtrack" and hang.
• Compilers and game search. Register allocation, instruction selection, and minimax with alpha-beta pruning are all backtracking with a prune rule.

function permute(a, k = 0, out = []) {  if (k === a.length) { out.push([...a]); return out; }  for (let i = k; i < a.length; i++) {    [a[k], a[i]] = [a[i], a[k]];            // CHOOSE    permute(a, k + 1, out);                 // EXPLORE    [a[k], a[i]] = [a[i], a[k]];            // UN-CHOOSE  }  return out;}

RecapCopy Anchor Link

• Backtracking is choose → explore → un-choose, driven by a recursion that walks a search tree depth-first.
• Prune on the way down: the instant a partial solution can't be completed, abandon it — don't finish a doomed guess.
• Two invariants keep it correct: partial states stay valid, and every mutation is undone on return so siblings start clean.
• It's DFS over implicit states; the call stack is the path from root to current node.
• Worst case is still exponential — the win is in the nodes you never visit.

Next up: Dynamic Programming Foundations — what to do when the same subproblems keep coming back, and brute-force exploration isn't enough.