Backtracking

How backtracking works

Imagine you're filling in a Sudoku grid. You write a 3 in the first empty cell, move on, and a few cells later realize there's no legal digit for some row. Instead of tearing up the page, you erase that last guess, try a 4, and continue. If that also dead-ends, you back up further — undoing as you go — until you either find a complete grid or prove none exists. That is backtracking, end to end.

Formally, backtracking organizes the candidate space as a tree. The root is the empty partial solution. Each child extends the parent by one decision (place a queen on column 4, choose digit 7 for cell 23, include item 5 in the subset). On every node the algorithm checks two things:

1. Goal test: is this a complete, valid solution? If yes, return it (or record it).
2. Pruning test: can any extension of this prefix possibly satisfy the constraints? If no, abandon the entire subtree without expanding it.

The pruning step is everything. Without it, you have brute force. With a tight pruning predicate you can chop trees that look astronomical down to a few thousand visited nodes. The 8-Queens tree has 8⁸ = 16,777,216 leaves; backtracking visits roughly 2,057 of them before enumerating all 92 solutions.

When to use backtracking

• The problem is to satisfy a set of constraints (find any valid assignment) or enumerate all valid assignments.
• Partial solutions are cheap to test for partial validity — you can fail fast.
• The state space is too large for brute force but lacks the heavy overlap that would let DP dominate.
• You need an exact answer, not an approximation.

If your problem has heavy subproblem overlap (Fibonacci, knapsack, edit distance), reach for dynamic programming. If you can tolerate an approximation, reach for a heuristic search like greedy or simulated annealing.

Backtracking vs DP vs branch-and-bound

	Backtracking	Dynamic programming	Branch-and-bound
Goal	Find valid assignment	Find optimal value	Find optimal value
Pruning	Constraint violation	Memoization (no work twice)	Bound-vs-best dominance
Overlapping subproblems	Few or none	Many (essential)	Few or none
Memory	O(depth)	O(states)	O(frontier)
Returns all solutions	Yes (natural)	No (just optimum)	No (just optimum)
Typical examples	N-Queens, Sudoku, SAT	Knapsack, edit distance	TSP, integer programming
Order of exploration	Depth-first	Bottom-up table fill	Best-first by bound

Branch-and-bound is backtracking's older cousin from operations research: it carries an upper-bound function that lets it prune a partial solution whose best-possible completion is already worse than the best known answer. The two algorithms blur into each other for optimization problems.

Pseudo-code (general template)

function backtrack(state):
    if state is complete:
        record(state)
        return
    for choice in candidates(state):
        if accept(state, choice):       # pruning test
            apply(state, choice)
            backtrack(state)
            undo(state, choice)         # critical: restore state

JavaScript: N-Queens, Sudoku, subset-sum

// 1) N-Queens: how many ways to place N queens on an N×N board?
function countNQueens(n) {
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  let count = 0;
  function place(row) {
    if (row === n) { count++; return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue;
      cols.add(c); diag1.add(row - c); diag2.add(row + c);
      place(row + 1);
      cols.delete(c); diag1.delete(row - c); diag2.delete(row + c);  // undo
    }
  }
  place(0);
  return count;
}

// 2) Sudoku solver — fills a 9×9 board in place.
function solveSudoku(b) {
  for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) {
    if (b[r][c] !== 0) continue;
    for (let d = 1; d <= 9; d++) {
      if (legal(b, r, c, d)) {
        b[r][c] = d;
        if (solveSudoku(b)) return true;
        b[r][c] = 0;     // undo
      }
    }
    return false;        // no digit fits — backtrack
  }
  return true;
}
function legal(b, r, c, d) {
  for (let i = 0; i < 9; i++)
    if (b[r][i] === d || b[i][c] === d) return false;
  const br = (r/3|0)*3, bc = (c/3|0)*3;
  for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++)
    if (b[br+i][bc+j] === d) return false;
  return true;
}

// 3) Subset-sum: find any subset of nums summing to target.
function subsetSum(nums, target, i = 0, picked = []) {
  if (target === 0) return picked.slice();
  if (i === nums.length || target < 0) return null;
  picked.push(nums[i]);
  const left = subsetSum(nums, target - nums[i], i + 1, picked);
  if (left) return left;
  picked.pop();    // undo
  return subsetSum(nums, target, i + 1, picked);
}

Python: same three problems

def count_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    count = 0
    def place(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for c in range(n):
            if c in cols or row - c in d1 or row + c in d2:
                continue
            cols.add(c); d1.add(row - c); d2.add(row + c)
            place(row + 1)
            cols.remove(c); d1.remove(row - c); d2.remove(row + c)
    place(0)
    return count

def solve_sudoku(b):
    for r in range(9):
        for c in range(9):
            if b[r][c] != 0: continue
            for d in range(1, 10):
                if legal(b, r, c, d):
                    b[r][c] = d
                    if solve_sudoku(b): return True
                    b[r][c] = 0
            return False
    return True

def legal(b, r, c, d):
    if any(b[r][i] == d or b[i][c] == d for i in range(9)): return False
    br, bc = 3*(r//3), 3*(c//3)
    return all(b[br+i][bc+j] != d for i in range(3) for j in range(3))

def subset_sum(nums, target, i=0, picked=None):
    if picked is None: picked = []
    if target == 0: return list(picked)
    if i == len(nums) or target < 0: return None
    picked.append(nums[i])
    left = subset_sum(nums, target - nums[i], i + 1, picked)
    if left: return left
    picked.pop()
    return subset_sum(nums, target, i + 1, picked)

Variants and pruning techniques

• Forward checking. After each assignment, propagate the consequences: remove the just-chosen value from the domains of all unassigned variables that share a constraint. If any domain becomes empty, fail immediately rather than waiting until you reach that variable.
• Constraint propagation (AC-3). Forward checking taken further: repeatedly tighten domains until reaching an arc-consistent state. Empties single-digit Sudoku domains in milliseconds before deep recursion ever runs.
• Most-constrained variable (MCV). Branch first on the variable with the smallest remaining domain. The empty Sudoku cell with only two legal digits halves the tree, the cell with seven octuples it.
• Least-constraining value (LCV). Within a chosen variable, try the value that rules out the fewest options for neighbours first.
• Iterative deepening. Run depth-limited DFS with increasing limits — combines DFS's low memory with BFS's optimality on tree-shaped state spaces.
• Conflict-directed backjumping. Instead of unwinding one level at a time, jump back to the most recent decision that was actually involved in the conflict. The seed idea behind modern SAT solvers.

Cost in real terms

The naive 8-Queens tree has 8⁸ ≈ 1.7 × 10⁷ leaves; pure column-and-diagonal pruning visits about 2,057 nodes — a 8,000× saving. For 16-Queens the gap explodes: 16¹⁶ ≈ 1.8 × 10¹⁹ leaves but classical backtracking visits roughly 1.5 million nodes (12 trillion times less work). Sudoku with constraint propagation handles a hand-tuned hard puzzle in under 1ms; without propagation, the same puzzle can take minutes or never finish.

Common bugs and edge cases

• Forgetting to undo state. The single most frequent backtracking bug. Every apply needs a matching undo on the path back up the recursion. Use immutable copies if you can afford the memory; the bug becomes structurally impossible.
• Returning success from the wrong frame. Solvers often need to bubble a "yes I solved it" boolean all the way up. Forgetting one return turns the whole recursion into a continuation that explores extra states or, worse, overwrites a solved board.
• Pruning too aggressively. A faulty accept predicate that rejects valid prefixes silently produces "no solution" on a solvable instance. Always test pruning logic on a known-soluble small instance first.
• Recursion depth. Python's default recursion limit is 1000; deep search trees (Sudoku solvers, SAT) hit it. Bump it with sys.setrecursionlimit or iterate with an explicit stack.
• Shared mutable structures. If your candidates function returns a reference to an internal list and another branch mutates it, behaviour becomes nondeterministic. Yield copies or freeze the candidate set.