Backtracking
Noun · Development
Definitions
Backtracking is an algorithmic technique that incrementally builds candidates for a solution and abandons a candidate (backtracks) as soon as it determines that the candidate cannot possibly lead to a valid solution. It is essentially a depth-first search of the solution space with pruning. The algorithm makes a choice, explores its consequences recursively, and if it reaches a dead end, undoes the last choice and tries the next alternative. Classic problems solved by backtracking include the N-Queens puzzle (placing N queens on a chessboard so none attack each other), solving Sudoku puzzles, generating all permutations or combinations of a set, and finding paths through mazes. Backtracking is more efficient than brute-force enumeration because pruning eliminates large portions of the search space that provably cannot contain solutions. Constraint satisfaction problems (CSPs) are a natural fit for backtracking. Enhancements include forward checking (preemptively eliminating future options that conflict with current choices) and constraint propagation. Many NP-hard optimization problems rely on backtracking as a foundation, often combined with heuristics.
In plain English: A problem-solving approach where you try a path, and if it does not work, you undo your last step and try a different one.
Example: "The Sudoku solver uses backtracking: it fills a cell, checks constraints, and undoes the choice if it hits a dead end."
Etymology
- 1956
- Derrick Henry Lehmer described a systematic trial-and-error approach for solving combinatorial problems, laying groundwork for what would become formal backtracking algorithms.
- 1960s
- The term 'backtracking' was popularized in computer science literature. It became the standard name for algorithms that incrementally build solutions and abandon paths that fail constraints.
- 1970s
- Backtracking became fundamental in AI (constraint satisfaction, game trees), compilers (parsing), and combinatorics. The 8-queens problem became its classic textbook illustration.
- 2000s-Present
- Backtracking remains essential in SAT solvers, Sudoku solvers, regular expression engines, and interview problems. Modern pruning techniques and heuristics dramatically improve its practical performance.
Origin Story
The Algorithm That Learns by Undoing Its Mistakes
Backtracking is an algorithmic technique that builds a solution incrementally, abandoning a path as soon as it determines the path cannot lead to a valid solution, then 'backing up' to try the next possibility. The concept has roots in the work of mathematicians and early computer scientists in the 1950s and 1960s. Derrick Henry Lehmer is often credited with formalizing early backtracking approaches for combinatorial problems in the 1950s. The technique was further developed and named by Solomon Golomb and Leonard Baumert in a 1965 paper, 'Backtrack Programming.' The classic illustration is the Eight Queens Problem: placing eight queens on a chessboard so none can attack another. A brute-force approach would check all 4.4 billion possible arrangements. Backtracking dramatically reduces this by placing queens one row at a time and immediately abandoning any placement that creates a conflict, pruning vast branches of the search tree. The technique became fundamental to constraint satisfaction problems, puzzle solving (Sudoku solvers almost universally use backtracking), compiler design (parsing ambiguous grammars), and artificial intelligence (early game-playing programs). Modern variants like backtracking with constraint propagation and backjumping make the approach even more efficient by learning from failures to skip larger portions of the search space.
Coined by: Solomon Golomb and Leonard Baumert
Context: Formally described in their 1965 paper 'Backtrack Programming,' building on earlier work by Lehmer.
Fun fact: A well-implemented backtracking Sudoku solver can solve even the hardest known Sudoku puzzles (rated by human difficulty) in under a millisecond, because the constraint propagation it performs is far more systematic than human reasoning.