Backtracking Search
Motivation
A constraint satisfaction problem (CSP) asks for an assignment of values to a set of variables that satisfies a given set of constraints. The brute-force approach of enumerating all \(d^n\) complete assignments (for \(n\) variables of domain size \(d\)) is intractable. Backtracking search is the standard improvement: a depth-first traversal of partial assignments that abandons a branch as soon as it violates any constraint, instead of waiting until the assignment is complete (Russell and Norvig 2020).
Backtracking is the workhorse algorithm for CSPs, SAT, scheduling, and combinatorial puzzles. With good variable and value ordering, it solves problem instances orders of magnitude larger than naive enumeration.
Problem
A CSP is a triple \((X, D, C)\):
- \(X = \{x_1, \ldots, x_n\}\) — variables.
- \(D = \{D_1, \ldots, D_n\}\) — finite domains; \(x_i\) takes values in \(D_i\).
- \(C\) — set of constraints, each restricting the joint values of some subset of variables.
A partial assignment binds some subset of variables to values in their domains. It is consistent if no constraint is violated by the bound variables. A complete consistent assignment is a solution; the algorithm should return one if it exists or report failure if none does.
Key Ideas
The central insight is early failure. The space of complete assignments has \(d^n\) leaves, but most of them share a common prefix that already violates a constraint. By checking constraints incrementally — after each variable is bound, not at the end — backtracking detects each conflict at the shallowest depth where it manifests and prunes the entire subtree below.
Three orthogonal choices control how much this pruning is worth:
Variable ordering — fail fast
The MRV (Minimum Remaining Values) heuristic chooses the variable with the fewest legal values left in its domain. Intuitively the most constrained variable, most likely to fail soon — and failing fast is good, because it prunes a large subtree before any work goes into it.
The degree heuristic breaks ties by choosing the variable involved in the most constraints with other unassigned variables. Most likely to constrain the rest of the search.
Value ordering — succeed fast
The Least Constraining Value (LCV) rule tries values in order of how few options they eliminate from neighboring variables. The intuition is opposite to MRV: when committing we want to leave room for the remaining variables to find a solution; only when choosing what to commit to (the variable) do we want to fail fast.
Constraint propagation — prune before committing
Plain backtracking only detects a conflict when it tries to extend an assignment to a variable whose domain has become empty. Forward checking front-loads this: when \(x = v\) is assigned, remove from each neighbor \(y\)’s domain any value inconsistent with \(v\). If any neighbor’s domain becomes empty, fail immediately rather than waiting for that variable’s turn.
Arc consistency goes further: iteratively remove from each variable’s domain any value with no consistent partner in some neighbor. Stronger than forward checking; a worthwhile preprocess and an effective per-step pruner. A solver running MAC (Maintaining Arc Consistency) — backtracking with full arc consistency at every node — is the modern default for CSPs.
Algorithm
function BACKTRACK(assignment):
if assignment is complete: return assignment
x = SELECT-UNASSIGNED-VARIABLE(assignment)
for each value v in ORDER-DOMAIN-VALUES(x, assignment):
if assignment ∪ {x = v} is consistent:
add {x = v} to assignment
result = BACKTRACK(assignment)
if result != failure: return result
remove {x = v} from assignment
return failureThe structure is a depth-first recursion on the tree of partial assignments. SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES are the variable- and value-ordering heuristics; an optional constraint-propagation step (forward checking, AC-3) typically runs after each assignment to tighten neighbor domains before recursing.
Walkthrough
2-coloring a 4-cycle
Four variables \(A, B, C, D\) in a cycle with constraints \(A \neq B\), \(B \neq C\), \(C \neq D\), \(D \neq A\), and domain \(\{R, B\}\) for each. Backtracking assigns variables in order \(A, B, C, D\), trying \(R\) before \(B\).
The full assignment space has \(2^4 = 16\) leaves; backtracking visits only \(2\) leaves before finding a solution. The pruning happens at the very first failure (\(B = R\) when \(A = R\)): the entire \(14\)-leaf subtree under that node would be skipped in any consistent search, but backtracking detects the conflict at depth \(2\) rather than at depth \(4\). Larger problems compound this benefit exponentially.
Correctness
Soundness. Any assignment returned has been checked to satisfy every constraint at each step, including the final check after the last variable is bound. So any returned assignment is a solution.
Completeness. The recursion explores every value of every variable in some order, pruning only when a partial assignment is already inconsistent. Since pruning never removes a subtree that could lead to a solution — pruning happens only after a constraint is violated, and no valid solution can extend a violating partial assignment — backtracking finds a solution whenever one exists, and reports failure otherwise.
Complexity and Tradeoffs
Backtracking has the same worst-case time complexity as enumeration — \(O(d^n)\) — because adversarial instances exist where no pruning is possible. The interest is empirical: on structured problems, modern backtracking with good heuristics and propagation handles instances with millions of variables routinely.
The space complexity is \(O(n)\) for the recursion stack plus the cost of representing the current partial assignment and propagated domains.
Backtracking is a special case of depth-first search on the tree of partial assignments. The optimization-and-pruning structure parallels alpha-beta search on game trees and branch-and-bound on integer programs: in each case, a depth-first traversal carries enough information to detect that a subtree cannot improve the answer, and skips it.
When to Use It
| Situation | Backtracking? |
|---|---|
| CSP with structure (sudoku, scheduling, graph coloring) | Yes — the default. Combine with MRV + LCV + arc consistency (MAC). |
| Pure SAT | Use a DPLL-based solver with CDCL — a specialized backtracking variant. |
| Integer programming | Use branch-and-bound — backtracking with LP relaxation bounds. |
| Optimization (find best, not any) | Add a bound check (branch-and-bound). |
| Continuous variables | Not applicable — backtracking requires finite domains. |
Variants
Backjumping. Standard backtracking returns to the immediate previous variable on failure. Backjumping returns directly to the most recent variable involved in the conflict, skipping intermediate decisions that were irrelevant to the failure. Conflict-directed backjumping further analyzes the conflict to compute the precise set of decisions that must be revised, often jumping back many levels.
Conflict-driven clause learning (CDCL). Modern SAT solvers extend backjumping: each conflict produces a learned clause that is added to the problem and used to prune future branches. This is the core technique behind every competitive SAT solver.