Skip to main content
Definition Website Computer and Technology

Backtracking

Subject: Computer and Technology noun /ˈbækˌtræk.ɪŋ/ 1 definition

  1. Definition (noun)

    Entry #60 · Updated

    Backtracking 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 selects http-client 2.4.0, which transitively requires tls-core ^3.0. Upon discovering that another direct dependency strictly pins tls-core 2.1.0, the solver backtracks, undoes the 2.4.0 selection, and tries http-client 2.0.3, which successfully resolves alongside tls-core 2.1.0.