Constraint propagation and backtracking search
Constraint propagation and backtracking search are core CSP methods: reduce domains by local consistency (propagation) and systematically search remaining choices (backtracking) with heuristics to solve combinatorial problems like scheduling, allocation, and puzzles.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Constraint propagation and backtracking search form the standard toolkit for solving constraint satisfaction problems (CSPs), which appear in many engineering tasks: register allocation, timetable and exam scheduling, resource allocation, configuration, and classical AI puzzles (Sudoku, map-colouring). Engineers use propagation to prune impossible values early and backtracking search (with heuristics) to find full solutions when propagation alone is insufficient.
Key ideas
Start from first principles and define every term.
Constraint satisfaction problem (CSP): A triple (X, D, C) where X = {X1, X2, ..., Xn} is a finite set of variables, D = {D1, D2, ..., Dn} is a set of domains where each Di is a finite set of possible values for Xi, and C is a set of constraints. Each constraint restricts the allowable combinations of values for some subset of variables. The task: find a complete assignment (value for each Xi from Di) that satisfies every constraint. Decision form: “Does a solution exist?”
- Assumption: domains are finite and discrete.
Partial assignment: An assignment that gives values to a subset of X. A partial assignment is consistent if it violates no constraint among the assigned variables.
Solution: A complete assignment that is consistent with all constraints.
Constraint graph: An undirected graph with a node per variable and an edge between Xi and Xj iff there exists a constraint involving both variables. Draw: for a CSP, draw nodes labeled Xi and edges for binary constraints; label edges with constraint relation if non-trivial.
Local consistency: Properties that relate a variable's domain with neighbors.
- Node consistency: Each value in Di satisfies unary constraints on Xi (if any). To enforce: remove values violating unary constraints.
- Arc-consistency (binary constraints): For a directed arc (Xi -> Xj), every value a in Di has at least one value b in Dj such that (a,b) satisfies the binary constraint between Xi and Xj. A CSP is arc-consistent if every arc is arc-consistent. For non-binary constraints, the analogous notion is generalized arc consistency (GAC): for each constraint over a scope S, every value of each Xi in S has a supporting tuple of values for S \ {Xi} (drawn from current domains) that satisfies the constraint.
- The most common algorithm: AC-3.
Constraint propagation: Repeatedly enforce a chosen local consistency (e.g., arc-consistency) to shrink domains; it can detect dead-ends early (empty domain) and reduce branching.
Backtracking search: Systematically build partial assignments variable by variable. At each step choose an unassigned variable, assign a value from its (possibly reduced) domain, and recurse. If a contradiction occurs (no legal values remain), backtrack.
Heuristics that dramatically improve backtracking:
- Minimum remaining values (MRV) or most-constrained variable: choose variable with smallest current domain size.
- Degree heuristic: tie-break MRV by choosing variable involved in most constraints on unassigned variables.
- Least constraining value: order values by how many values they rule out in neighbours (prefer fewer eliminations).
- Forward checking: After assigning Xi = a, temporarily remove incompatible values from neighbours' domains; if any domain becomes empty, reject assignment early.
- Maintaining arc-consistency (MAC): After each assignment, run a full arc-consistency algorithm (AC-3) on reduced domains instead of simple forward checking. Stronger pruning, more expensive per node.
Complexity and computational facts:
- General CSP decision is NP-complete (reduction from SAT or graph-colouring). So worst-case exponential time in n is expected for arbitrary CSPs.
- Many structured CSPs are tractable (tree-structured constraint graphs solvable in linear time using directional arc-consistency and back-substitution).
What to draw for exam answers:
- For a constraint graph: draw nodes X1..Xn, draw edges for binary constraints, label edges with relation symbol (e.g., ≠ for map-colouring). For AC-3 trace: show a queue of arcs (Xi->Xj); for each arc show domain values and which values get removed.
Exact algorithm statements to memorize (universities expect formal descriptions):
- AC-3 invariant: While queue not empty, remove arc (Xi->Xj); for each a in Di if no b in Dj satisfies constraint Ri,j(a,b), remove a from Di and enqueue all arcs (Xk->Xi) for k ≠ j. Terminate when no change.
- Backtracking search (recursive): choose unassigned variable X using heuristic; for each value v in current domain of X (value ordering heuristic), if v consistent with current partial assignment then extend assignment and (optionally) propagate (forward checking or MAC); if recursive call succeeds return solution; else undo and try next v; if no v succeeds return failure.
Formulas
(Here list key complexity/syntax lines to remember.)
AC-3 worst-case time = O(m · d^3)where m = number of directed arcs (two per undirected binary constraint) and d = size of the largest domain; this follows because Revise can cost O(d^2) and each arc may be requeued O(d) times.- symbols: m = number of arcs (directed), d = max |Di|. Equivalently O(e · d^3) with e = number of undirected binary constraints, up to a factor of 2.
Backtracking worst-case states ≈ O(d^n)where n = number of variables and d = typical domain size (exponential time).- Tree-structured binary CSPs solvable in O(n · d^2) time using directional arc-consistency and back-substitution, where n = |X| and d = max |Di|.
Pseudo-syntax: assignment[X] = vmeans put value v for variable X in the current assignment.Revise(Xi, Xj): remove values a in Di for which ∄b in Dj s.t. constraint(Xi,Xj) satisfied.Select-Unassigned-Variable(assignment): returns Xi using MRV (+ degree tie-break).Expand with forward checking: after assignment[X]=v, for each unassigned neighbor Y, D(Y) ← {b in D(Y) | (v,b) satisfies constraint(X,Y)}.
Worked examples
Example 1 — Map colouring (model-answer, stepwise backtracking + forward checking). Problem: Variables X = {WA, NT, SA, Q, NSW, V, T}. Domains all {R,G,B}. Constraints: adjacent regions must have different colours (binary ≠). Use MRV and forward checking. Variable order chosen by MRV at each step; initial all domain sizes = 3 so break ties by fixed order [WA,NT,SA,Q,NSW,V,T]. Step 1: Select WA (tie-break). Try WA=R. Forward check: remove R from domains of neighbors {NT,SA}. Now NT,SA domains = {G,B}. Step 2: MRV chooses NT or SA (both domain size 2). Tie-break choose NT. Try NT=G. Forward check: remove G from neighbors of NT (WA already assigned, SA loses G if present). SA domain becomes {B}. Step 3: MRV picks SA (domain size 1). Assign SA=B. Forward check: SA neighbors (NT,WA,Q,V,NSW) remove B where present — Q loses B if present, V loses B, NSW loses B. Now Q domain {R,G}, V {R,G}, NSW {R,G}. Step 4: MRV pick Q (domain size 2 tie; choose Q). Try Q=R. Forward check: NSW removes R → NSW {G}. Step 5: MRV picks NSW (domain size 1). Assign NSW=G. Forward check: V removes G → V {R}. Step 6: MRV picks V (domain 1). Assign V=R. Forward check: no change (T has no neighbors in this map). Step 7: MRV picks T (domain size 3). Try T=G. No contradictions remain. All variables assigned. Solution (one valid): {WA=R, NT=G, SA=B, Q=R, NSW=G, V=R, T=G}. Show work and domain reductions in exam answer.
Example 2 — Run AC-3 on small binary CSP. Problem: Variables A,B,C with domains D(A)={1,2}, D(B)={1,2}, D(C)={1,2,3}. Constraints: A≠B, B< C (i.e., B must be strictly less than C). Initial arcs: (A->B), (B->A), (B->C), (C->B). Step-by-step (queue initialized with all arcs):
- Pop (A->B). For each a in D(A): does ∃b in D(B) with a≠b? For a=1, b=2 exists; for a=2, b=1 exists. No deletion.
- Pop (B->A): symmetric, no deletion.
- Pop (B->C): for b in D(B): b=1 needs c>1 → c in {2,3} exists; b=2 needs c>2 → c in {3} exists. No deletion.
- Pop (C->B): for c=1, need b<c so b in { } (none) → remove c=1 from D(C). D(C) becomes {2,3}. No new arcs enqueued because the only neighbor of C is B (excluded by the AC-3 rule).
- Queue empty. Result: Domains reduced to D(A)={1,2}, D(B)={1,2}, D(C)={2,3}. AC-3 detected removal of c=1. If any domain had become empty, AC-3 would report inconsistency. Show queue trace as diagram in exam.
Common mistakes
- Forgetting to restore domains when backtracking if implementing forward checking manually. Always record changes on a stack and undo on backtrack.
- Applying MRV without tie-breaking: leads to nondeterministic answers in exams—always state tie-break rule (e.g., lowest index variable).
- Mixing up directionality in AC-3: arc (Xi->Xj) tests values in Di against Dj, not vice versa.
- Wrong complexity claims: AC-3 is often quoted as O(ed^2) or O(cd^3); state assumptions (binary constraints, cost of revise) and derive carefully.
For your exam
Kinds of questions you will get:
- Definitions and short notes: define CSP, arc-consistency, MRV, forward checking, MAC, and state differences.
- Derivations/proofs: show why tree-structured CSPs are solvable in linear time (explain directional arc-consistency + back-substitution). Derive AC-3 complexity with assumptions.
- Trace/diagrams: run AC-3 on a small CSP and show queue contents and domain changes; draw a constraint graph and indicate node/edge labels.
- Algorithm design/programming: write backtracking with forward checking pseudocode and explain heuristics.
- Numerical/stepwise: simulate backtracking with MRV on a small map-colouring and show the assignments and domain reductions. What a full-marks answer includes:
- Exact definitions with bold names, assumptions stated (finite domains, binary vs non-binary constraints), correct algorithm pseudocode or clear stepwise trace, diagrams when asked (constraint graph, AC-3 queue), and complexity statements with short justification.
Quick check
- What is the test performed by Revise(Xi, Xj) in AC-3?
- Give two variable-ordering heuristics used in CSP backtracking.
- Does arc-consistency guarantee a solution exists? Explain briefly. Answers: 1) Remove a in Di if ∄b in Dj such that constraint(Xi,Xj) satisfied. 2) MRV (minimum remaining values) and degree heuristic (most constrained by number of unassigned neighbours). 3) No — arc-consistency only prunes domains (may leave non-empty domains yet no global solution).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?