Backtracking

Backtracking builds a solution incrementally, one component at a time, and at each step checks whether the partial solution can still lead to a valid complete solution. If not, it removes the last added component and tries the next alternative. This is equivalent to a depth-first search of a tree of partial candidates, pruning branches that cannot satisfy the constraints.²

The algorithm is often expressed recursively: a function explores a partial candidate; if it is complete and valid, it is recorded; otherwise, it extends the candidate with each possible next element and recurses. The key is the promising function, which quickly rejects hopeless branches, reducing the search space dramatically compared to brute-force enumeration.

Backtracking is used to solve combinatorial puzzles and optimization problems. The eight queens puzzle, where eight queens must be placed on a chessboard so that none attack another, is a canonical example; backtracking places queens one by one and backtracks when a conflict arises.³ Other applications include Sudoku solving, the Hamiltonian path problem, the knapsack problem, and constraint satisfaction problems in artificial intelligence, such as map coloring and scheduling.

In compiler design, backtracking appears in parsing (e.g., in some top-down parsers) and in regular expression matching, where the engine tries different paths and backtracks on failure. It is also used in logic programming languages like Prolog, where unification and search rely on backtracking to explore alternative proofs.

The term "backtracking" was coined by American mathematician D. H. Lehmer in the 1950s, though the technique itself is older. The eight queens puzzle was first solved by Max Bezzel in 1848 and later by Franz Nauck in 1850, who used a form of backtracking. The method was formalized in the 1960s by Robert Floyd and others, and its relationship to depth-first search was clarified by Donald Knuth in his influential work on the dancing links algorithm, which efficiently implements backtracking for exact cover problems.⁴

Theoretically, backtracking is a general algorithm for finding all (or some) solutions to computational problems, especially constraint satisfaction problems. Its worst-case time complexity is exponential, but with good pruning it can be efficient in practice. The technique is closely related to branch and bound, which adds bounding functions to prune suboptimal branches in optimization problems.

Backtracking has subtle variations: forward checking and constraint propagation are enhancements that reduce the search space by eliminating values from future variables before recursion. The minimum remaining values heuristic selects the variable with the fewest legal values, improving efficiency. In the context of exact cover, Knuth's dancing links uses doubly linked lists to quickly remove and restore rows, making backtracking extremely fast for puzzles like pentominoes.

Backtracking is also used in computational biology for sequence alignment and in cryptography for solving subset-sum problems. A notable edge case is that backtracking can be implemented iteratively with an explicit stack, avoiding recursion depth limits. In some problems, such as the n-queens problem, symmetry breaking can reduce the search space by a factor of 8, a technique often overlooked in introductory treatments.

Constraint-satisfaction problem

A problem where one must find a state satisfying a set of constraints, e.g., Sudoku.

Pruning

The act of discarding a branch of the search tree that cannot lead to a solution.

Depth-first search

A traversal of a tree or graph that explores as far as possible along each branch before backtracking.

Exact cover

A problem of selecting rows in a binary matrix so that each column has exactly one 1.