A tree-search mechanism that recursively assigns values to decision variables, propagates consequences, and reverts (backtracks) assignments when a contradiction or dead end is reached to systematically explore alternative assignments.

Principle

Explore a search space depth-first, commit to choices incrementally, detect infeasible branches early, and undo recent choices to try alternatives, thereby navigating a combinatorial space without enumerating all assignments at once.

Demonstration

When solving a CSP with variables X, Y, Z, assign X = a, propagate constraints to reduce Y's domain, then assign Y = b; if a constraint later falsifies with Z, backtrack to change Y or X and continue exploring other combinations.

Misapplication

Using naive backtracking without propagation or heuristics (e.g., fixed variable order irrespective of remaining domain sizes) leads to excessive recomputation and exploration of irrelevant branches.

Consequence

Backtracking search yields complete decision procedures for finite CSPs and SAT, enabling correct solutions when combined with pruning methods; its runtime depends heavily on branching order and pruning effectiveness.

Reversal

The inverse is blind breadth-first or unordered enumeration of all assignments without reverting, which preserves completeness but eliminates the targeted undo-and-retry efficiency backtracking provides.

Boundary

Applies to discrete, finite decision spaces where assignments can be reverted; it excludes continuous search without discretization and techniques that do not support systematic undo of decisions (e.g., purely local search without backtracking).

Semantic Tension

Tensions arise with local-search heuristics: local search explores by transforming a full assignment iteratively and may escape backtracking's systematic guarantees for faster typical-case performance but without completeness.

Synthesis

Backtracking search is the controlled mechanism of committing to partial solutions, using deduction to prune impossible extensions, and reverting those commitments to methodically traverse the combinatorial landscape until solutions or exhaustion.