Backtracking
Subject: Computer and Technology noun /ˈbækˌtræk.ɪŋ/ 1 definition
- computer-science
- search-algorithms
- algorithm-design
- constraint-satisfaction
-
Definition (noun)
Entry #60 · UpdatedBacktracking is a general-purpose algorithmic technique for solving combinatorial, decision, and constraint-satisfaction problems by incrementally constructing candidate solutions one step at a time. At each decision point in an implicit state-space tree, the algorithm explores a viable choice—typically via depth-first traversal—and immediately abandons, or prunes, the branch if the partial candidate violates a constraint, undoing its most recent step to test alternative choices. By discarding infeasible subtrees early rather than evaluating every complete configuration as naive brute-force search does, backtracking reduces computational effort while still guaranteeing completeness across all valid solutions.
Common Forms
Recursive Backtracking: Uses the program's call stack to implicitly record each decision state, automatically reverting changes when a recursive branch hits a dead end and returns.
Iterative Backtracking: Replaces recursion with an explicit stack or state table to track choice points manually, avoiding call-stack overflow when exploring deeply nested search trees.
Look-Ahead Backtracking: Pairs state-space search with techniques such as forward checking or arc consistency to prune incompatible values from unassigned variables before descending further.
Non-Chronological Backtracking (Backjumping): Analyzes conflict causes on failure and jumps directly back to the earlier decision responsible for the contradiction, bypassing unrelated intermediate levels.
Example
When a package manager resolves dependencies for a project requiring
http-client >= 2.0, it speculatively selectshttp-client 2.4.0, which transitively requirestls-core ^3.0. Upon discovering that another direct dependency strictly pinstls-core 2.1.0, the solver backtracks, undoes the2.4.0selection, and trieshttp-client 2.0.3, which successfully resolves alongsidetls-core 2.1.0.