Why pruning is everything
Backtracking is only practical because of pruning: discarding partial candidates that cannot lead to a solution. Without it, backtracking degenerates into full enumeration. The art lies in detecting failure as high in the tree as possible, where one cut removes an entire subtree.
Pruning techniques
- Constraint propagation: after a choice, tighten the legal options of related variables, and fail if any variable runs out of options. Sudoku and n queens lean on this.
- Bounding: maintain a best solution so far and abandon any branch whose optimistic estimate cannot beat it. This is the heart of branch and bound.
- Symmetry breaking: fix an arbitrary choice, such as the first queen on the left half, to skip mirror-image duplicates.
- Ordering: try the most constrained variable or most promising value first, so failures surface early and good solutions appear sooner.
Cheap checks pay off
A prune is worthwhile when its cost is small next to the subtree it eliminates. Maintaining incremental data, like used-digit bitmasks updated on each choice and undone on backtrack, keeps each check constant time while saving exponential work.
Key idea
Pruning, through constraint propagation, bounding, symmetry breaking, and smart ordering, kills doomed branches near the root, turning otherwise hopeless searches into tractable ones.