## Definition **Backtracking search** is the basic algorithm for solving a [[Constraint Satisfaction Problem]]. It is a depth-first search of partial assignments: extend one variable at a time; check constraints; if violated, undo and try a different value. ## Algorithm ``` function Backtrack(assignment, csp): if assignment is complete: return assignment var ← SelectUnassigned(csp, assignment) for each value in OrderDomain(var, assignment, csp): if value is consistent with assignment: add {var = value} to assignment result ← Backtrack(assignment, csp) if result ≠ failure: return result remove {var = value} from assignment return failure ``` ## Why It's Better Than Generate-and-Test Generate-and-test would enumerate all $\prod |D_i|$ complete assignments, then check each. Backtracking aborts as soon as *any* partial assignment violates a constraint — pruning huge swaths of the search tree. ## Boosters Pure backtracking is exponential. Three additions make it practical: 1. **Variable ordering** — *MRV*: pick the variable with the fewest remaining values. Fail fast. 2. **Value ordering** — *LCV*: try the least constraining value first. Succeed fast. 3. **Inference** — *forward checking* or full [[Arc Consistency AC-3]] after each assignment, pruning domains of other variables. These reduce the effective branching factor and prune dead branches early. ## Forward Checking After assigning $X = v$, for each unassigned $Y$ connected to $X$ by a constraint, remove from $D_Y$ any value inconsistent with $v$. If any domain becomes empty, backtrack immediately. Cheap; catches some failures. ## Maintaining Arc Consistency (MAC) Stronger: after every assignment, run [[Arc Consistency AC-3]] to *transitively* propagate constraints. More expensive per step, but explores far fewer nodes for hard problems. ## Conflict-Directed Backjumping When backtracking, instead of going up one level, jump to the deepest variable that caused the conflict. Cuts entire useless subtrees. Underlies modern SAT/CSP solvers. ## Limits Even with all boosters, backtracking is **NP-hard** in the worst case. For very hard CSPs, **local search** (e.g., min-conflicts) or modern **conflict-driven** solvers may be preferable. ## Related - [[Constraint Satisfaction Problem]] - [[Arc Consistency AC-3]] - [[Constraint Propagation]] - [[Depth-First Search]]