Backtracking and Pruning¶

Systematic enumeration of a solution space can be made efficient by abandoning partial solutions as soon as they violate constraints, pruning entire subtrees of the search space.

Tension Addressed¶

Generality vs. Efficiency

Recognizable As¶

Recursive exploration with constraint checking at each step; "undo" operations when backtracking; early termination branches.

Canonical Sources¶

Walker, "An Efficient Method for Generating N-Queens Solutions," 1960; Knuth, "Dancing Links," 2000

Transfers To¶

Constraint satisfaction, SAT solvers, game AI (minimax), compiler optimization, puzzle solving, combinatorial optimization

The effectiveness of backtracking depends entirely on pruning quality. Good pruning functions (constraint propagation, bound estimation) can make intractable problems practical.