Backtracking

Backtracking is a systematic way to search for solutions by building candidates one decision at a time, and the moment a partial candidate cannot possibly lead to a valid solution, abandoning it and undoing the last decision. It is depth-first search over the space of partial candidates.

The Core Pattern

Every backtracking algorithm has the same skeleton:

1. Choose — make the next decision (e.g. place a queen, pick a value).
2. Check — is the partial solution still valid? If not, prune and undo.
3. Recurse — move to the next decision.
4. Undo — on failure, remove the last choice and try the next option.

function solve(state):
  if state is complete: record solution; return
  for each candidate in ordered options:
    if valid(state + candidate):
      apply(candidate)
      if solve(state) succeeds: return true
      undo(candidate)          # backtrack
  return false

Key Ideas

Pruning is what separates backtracking from brute force. By checking constraints during construction — rather than after a full candidate exists — the algorithm cuts off entire subtrees. N-Queens prunes every attacked position before recursing; without pruning it would enumerate C(n², n) boards instead of exploring only O(n!) safe partial placements.

Undo must be exact. Each recursive frame must restore the state it modified, or later branches will see corrupt state. This is why backtracking solutions mutate a shared board/array rather than copying it.

Famous Backtracking Problems

Backtracking vs Related Techniques

Backtracking explores the space and prunes but stores no table; DP shares subproblems. A problem with overlapping subproblems belongs in DP; a problem where each branch is essentially unique (N-Queens, Sudoku) belongs in backtracking.

Optimization Techniques

• Heuristic ordering (MRV) — choose the decision with the fewest options first; this prunes earlier and dramatically shrinks the tree.
• Forward checking — after each placement, eliminate candidates that became impossible.
• Symmetry breaking — skip mirror images and rotations of equivalent solutions.
• Iterative deepening — combine DFS with a depth limit for state spaces of unknown size.

Practice Trajectory

Start with permutations and subsets, then N-Queens (the classic board), then Sudoku (multi-constraint), then graph coloring and Hamiltonian paths. For each, focus on the prune condition — that’s where the performance lives.