Backtracking search assigns variables one at a time. After each assignment, it checks whether constraints are still satisfiable; if not, it undoes the assignment and tries another value.
Algorithm
``` function backtrack(assignment, csp): if assignment is complete: return assignment var = select_unassigned_variable(csp, assignment) for value in order_domain_values(var, csp, assignment): if value is consistent with assignment: assignment[var] = value inferences = inference(csp, var, value) if inferences != failure: result = backtrack(assignment, csp + inferences) if result: return result del assignment[var] undo inferences return failure ```
Critical design choices
The naive version is exponential and slow on anything nontrivial. Three knobs make it fast:
### Variable ordering: minimum remaining values (MRV)
Pick the variable with the smallest remaining legal-value domain. Tie-break with degree heuristic: variable involved in most constraints with unassigned variables. The intuition: failing fast in the most constrained corner of the problem prunes the largest amount of search.
### Value ordering: least constraining value
For the chosen variable, try values that rule out the fewest options for neighboring variables first. The intuition: if you're going to succeed, do it with the choice that leaves the most flexibility.
### Forward checking and constraint propagation
After assigning a value, remove that value (and any newly inconsistent values) from neighbors' domains. If any neighbor's domain empties, backtrack immediately rather than continuing.
Constraint propagation hierarchy
- Forward checking: prune only neighbors of the just-assigned variable.
- Arc consistency (AC-3): for every pair of variables, ensure each value has at least one supporting value in the neighbor's domain. Iteratively propagate.
- Path consistency, k-consistency: stronger and stronger; more expensive per step.
In practice, AC-3 plus MRV plus least-constraining-value solves most academically interesting CSPs efficiently. Industrial CSP solvers add clause learning on top.
Backjumping and CBJ
When backtracking fails, instead of backtracking to the immediately previous variable, jump back to the variable that caused the failure. Conflict-directed backjumping (CBJ) explicitly tracks which variables participated in the failed constraints and jumps there. Modern solvers do something more sophisticated — conflict-driven clause learning (CDCL) — that records the failure as a learned constraint for future use.