Constraint Satisfaction Problems
Backtracking, propagation and smart variable ordering.
Coloring a map, placing queens, filling a sudoku and timetabling exams look like different puzzles, but a constraint solver sees one shape in all of them: variables, domains and constraints. Describe a problem that way and a single engine solves it. This lesson builds that engine, from backtracking search to the heuristics and propagation that make it fast.
What you’ll learn
- Formulate problems as CSPs and draw their constraint graphs.
- Write backtracking search and show why branching on one variable per node shrinks the tree from leaves to .
- Apply MRV, the degree heuristic and LCV, and justify "fail first, succeed first".
- Run forward checking and AC-3 by hand, and derive AC-3's running time.
- Explain why tree-structured CSPs take only time, and when local search is the better tool.
Variables, domains, constraints
A constraint satisfaction problem has three parts: variables ; a domain of possible values for each; and constraints, each a pair listing which combinations of values the variables in its scope may take. Unlike path-finding, nothing about the route matters: only the final assignment.
| Problem | Variables | Domains | Constraints |
|---|---|---|---|
| Map coloring (Australia) | the 7 regions | {red, green, blue} | for the 9 pairs of neighbors |
| -queens | = row of the queen in column | and for all | |
| Sudoku (9×9) | the 81 cells | ; a given has one value | 27 Alldiff constraints (rows, columns, boxes), i.e. 810 binary constraints |
| Job-shop scheduling | start time of each task | integers up to a horizon | precedences ; one task per machine at a time |
The constraint graph exposes structure. In Australia, South Australia touches five regions while Tasmania touches none, so Tasmania is an independent subproblem. Generality has a price: graph 3-coloring is a special case, and deciding it is NP-complete, so no known algorithm solves every CSP in polynomial time. The realistic goal is speed on the instances that occur in practice.
With one variable per column (domain: the 8 rows), how many complete assignments does 8-queens have?
Show the answer
C.
Each of the 8 column variables independently takes one of 8 rows: . The formulation already guarantees one queen per column, so the constraints only have to rule out shared rows and diagonals.
Backtracking search
Treat the CSP as a search problem: a state is a partial assignment, an action assigns a value to an unassigned variable, and the goal test checks for a complete, consistent assignment. Formulated naively, this search tree is enormous, but one observation collapses it.
Naively, any of the variables can get any of values at the root, any of the remaining at the next level, and so on:
But assignment is commutative: is the same state whichever came first, so every complete assignment sits at leaves. Branching on a single variable at each node removes the duplicates:
For Australia (, ) that is the difference between eleven million leaves and 2,187:
Backtracking prunes on top of this: a partial assignment of variables that violates a constraint is abandoned at once, discarding all of its completions unseen.
function BACKTRACKING-SEARCH(csp) returns a solution or failure
return BACKTRACK(csp, {})
function BACKTRACK(csp, assignment) returns a solution or failure
if assignment is complete then return assignment
var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do
if value is consistent with assignment then
add {var = value} to assignment
inferences ← INFERENCE(csp, var, value) // e.g. forward checking, MAC
if inferences ≠ failure then
add inferences to csp
result ← BACKTRACK(csp, assignment)
if result ≠ failure then return result
remove inferences from csp
remove {var = value} from assignment
return failureThe three procedures in capitals are the hooks the rest of this lesson fills in. The search is depth-first, so it needs memory linear in (plus what it saves to undo inferences), and time in the worst case.
Why does branching on a single variable at each node lose no solutions?
- Because the chosen variable is always the most constrained one
- Because an assignment is a set of variable–value pairs, so order is irrelevant: every complete assignment still lies on exactly one path
- Because backtracking later revisits the other variable orders
- It does lose solutions, but only ones symmetric to others
Show the answer
B. Because an assignment is a set of variable–value pairs, so order is irrelevant: every complete assignment still lies on exactly one path
Assignments commute. Follow any complete assignment down the tree, taking at each node the value it gives the branching variable: you reach exactly one leaf. Every solution survives, minus its duplicates. The branching variable may even differ between nodes, which is what MRV exploits.
Choosing the next variable and value
Backtracking leaves two choices open: which variable to assign next, and in which order to try its values. Good answers can make the difference between seconds and hours.
- Minimum remaining values (MRV): pick the variable with the fewest legal values left. If some variable has none, MRV picks it at once and the dead end surfaces immediately.
- Degree heuristic: break MRV's ties with the variable involved in the most constraints on unassigned variables. In an uncolored Australia every region has three colors left, and South Australia, with five neighbors, goes first.
- Least constraining value (LCV): try first the value that rules out the fewest values in the neighbors' domains.
Think first MRV picks the most constrained variable, but LCV picks the least constraining value. Isn't that inconsistent?
No: the two choices play different roles. Every variable must be assigned eventually, so tackling the hardest one first costs nothing and exposes failure near the root, where pruning saves the most ("fail first"). But only one value per variable has to work, so you try the most promising one first ("succeed first"). If you wanted all solutions, or there were none, value order would not matter at all: every value gets tried anyway.
Propagation: forward checking and arc consistency
Heuristics choose well; propagation removes choices. Forward checking runs after each assignment : it deletes every value that conflicts with from the domains of the unassigned neighbors, and backtracks at once if a domain empties. It looks only one step ahead. After WA = red and Q = green it leaves NT and SA . They are neighbors, so this is a dead end, but forward checking does not notice.
function AC-3(csp) returns false if an inconsistency is found, else true
queue ← all arcs (Xi, Xj) of csp // both directions of every constraint
while queue is not empty do
(Xi, Xj) ← POP(queue)
if REVISE(csp, Xi, Xj) then
if Di is empty then return false
for each Xk in NEIGHBORS(Xi) − {Xj} do
add (Xk, Xi) to queue
return true
function REVISE(csp, Xi, Xj) returns true iff Di was revised
revised ← false
for each x in Di do
if no y in Dj satisfies the constraint between Xi and Xj then
delete x from Di; revised ← true
return revisedAC-3 (Mackworth, 1977). When shrinks, every arc pointing into is rechecked, because some neighbor's value may just have lost its only support.
Take a binary CSP with variables, constraints and domains of size at most . Each constraint gives two arcs, and all of them start in the queue:
An arc is queued again only when loses a value, which happens at most times. Each such loss queues at most arcs:
Each REVISE tests every against every :
Multiply. AC-4 (Mohr & Henderson, 1986) brings this down to , which is optimal: checking every arc once already costs that much in the worst case.
WA = red and Q = green, and forward checking has left NT and SA . What does AC-3 do?
- Nothing: no domain is empty
- It assigns blue to both NT and SA
- It finds that blue in SA has no support in NT (or vice versa), empties a domain and reports failure, so the solver backtracks at once
- It deletes red from New South Wales
Show the answer
C. It finds that blue in SA has no support in NT (or vice versa), empties a domain and reports failure, so the solver backtracks at once
The arc (SA, NT) is inconsistent: SA = blue needs a different color in NT, and NT has only blue. REVISE empties a domain, AC-3 returns false, and the solver abandons Q = green immediately instead of discovering the clash several levels deeper.
Running AC-3 after every assignment, seeded with the arcs from the unassigned neighbors of the variable just assigned, is MAC. It prunes everything forward checking prunes and more, at a higher cost per node, a trade that usually pays.
Structure, local search and SAT
Heuristics and propagation work on any CSP. Exploiting the shape of the constraint graph can do far better.
- Independent subproblems. Connected components can be solved separately: components of variables cost instead of .
- Trees. If the constraint graph is a tree, order the variables so that each comes after its parent, make every arc (parent, child) consistent from the leaves up, then assign from the root down. Every value left in a parent has a support in each child, so the downward pass never backtracks.
When even that is too slow, give up completeness. Local search starts from a complete assignment that violates some constraints and repairs it. The min-conflicts heuristic repeatedly picks a conflicted variable and gives it the value that violates the fewest constraints. On -queens, its running time after the initial placement is roughly independent of : it solves the million-queens problem in about 50 steps on average. It can never prove that no solution exists, though.
Finally, a Boolean CSP whose constraints are clauses is the satisfiability problem, SAT. SAT solvers run this lesson's recipe in specialized form (backtracking, propagation of unit clauses, dynamic variable ordering), plus one addition: they learn a new clause from every conflict.
Key takeaways
- A CSP is , and a solution is a complete, consistent assignment. General CSPs are NP-complete, so structure and inference are what make real instances easy.
- Backtracking is depth-first search that branches on one variable per node ( leaves, not ) and abandons a partial assignment as soon as it violates a constraint.
- MRV with degree tie-breaking fails first; LCV succeeds first. Value order matters only when you stop at the first solution.
- Forward checking prunes the neighbors of each new assignment; AC-3 enforces arc consistency everywhere in , and MAC reruns it after every assignment.
- Tree-structured CSPs take ; cutset conditioning extends this to near-trees, and min-conflicts local search handles huge instances without a completeness guarantee.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A binary CSP has variables, constraints and domains of size . What is AC-3's worst-case running time?
Show the answer
D.
Each of the arcs re-enters the queue at most times, once per value its target can lose, so there are revisions, each costing .
No region of Australia is colored yet, and MRV breaks ties with the degree heuristic. Which region is assigned first?
- Western Australia, the first in the list
- South Australia
- Tasmania
- New South Wales
Show the answer
B. South Australia
All seven regions tie with three legal colors, so the degree heuristic decides: South Australia constrains five unassigned regions, more than any other.
When does the order in which values are tried make no difference to the total work of backtracking?
- When MRV chooses the variables
- When the constraint graph is a tree
- When every domain has the same size
- When you need all solutions, or the problem has none
Show the answer
D. When you need all solutions, or the problem has none
Then every value of every variable along each path is tried regardless of order. Value ordering pays off only when the search can stop at the first solution.
Which statement about forward checking (FC) and maintaining arc consistency (MAC) is true?
- MAC prunes every value FC prunes, and possibly more, at a higher cost per node
- FC and MAC always prune exactly the same values
- With MAC, backtracking is never needed
- MAC only works on tree-structured CSPs
Show the answer
A. MAC prunes every value FC prunes, and possibly more, at a higher cost per node
FC makes only the arcs from unassigned neighbors into the new assignment consistent; MAC starts from those arcs and keeps propagating. It catches failures such as NT = SA = {blue} that FC misses.
A CSP's constraint graph is a tree with variables and values each. Roughly how many value-pair checks does the tree algorithm's upward pass need in the worst case?
- About
- About
- About
- About
Show the answer
B. About
One REVISE per edge, of them, each comparing up to value pairs: about checks. The tree shape turns an exponential problem into a linear one.
Go deeper
- Arc Consistency & Propagation · AC-3, path consistency and tree-structured CSPs.
- SAT Solving: DPLL & CDCL · The engines behind modern verification and planning.
- Local Search & Metaheuristics · Hill climbing, simulated annealing and genetic algorithms.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 6.
- R. M. Haralick & G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems," Artificial Intelligence 14(3) (1980), 263–313.
- A. K. Mackworth, "Consistency in networks of relations," Artificial Intelligence 8(1) (1977), 99–118.
- R. Dechter, Constraint Processing (Morgan Kaufmann, 2003).