Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

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 (X,D,C)(\mathcal X,\mathcal D,\mathcal C) and draw their constraint graphs.
  • Write backtracking search and show why branching on one variable per node shrinks the tree from n! dnn!\,d^n leaves to dnd^n.
  • 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 O(ed3)\order{ed^3} running time.
  • Explain why tree-structured CSPs take only O(nd2)\order{nd^2} time, and when local search is the better tool.

Variables, domains, constraints

A constraint satisfaction problem has three parts: variables X1,…,XnX_1,\dots,X_n; a domain DiD_i of possible values for each; and constraints, each a pair ⟨scope,relation⟩\langle\text{scope},\text{relation}\rangle listing which combinations of values the variables in its scope may take. Unlike path-finding, nothing about the route matters: only the final assignment.

ProblemVariablesDomainsConstraints
Map coloring (Australia)the 7 regions{red, green, blue}Xi≠XjX_i\neq X_j for the 9 pairs of neighbors
nn-queensQiQ_i = row of the queen in column ii{1,…,n}\{1,\dots,n\}Qi≠QjQ_i\neq Q_j and ∣Qi−Qj∣≠∣i−j∣|Q_i-Q_j|\neq|i-j| for all i<ji<j
Sudoku (9×9)the 81 cells{1,…,9}\{1,\dots,9\}; a given has one value27 Alldiff constraints (rows, columns, boxes), i.e. 810 binary ≠\neq constraints
Job-shop schedulingstart time SaS_a of each taskintegers up to a horizonprecedences Sa+da≤SbS_a+d_a\le S_b; one task per machine at a time
A global constraint such as Alldiff (all values distinct) can be split into binary ≠\neq constraints, but solvers often keep it whole because it supports stronger reasoning.

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.

Check your understanding

With one variable per column (domain: the 8 rows), how many complete assignments does 8-queens have?

  1. 8!=40,3208!=40{,}320
  2. (648)≈4.4×109\binom{64}{8}\approx4.4\times10^9
  3. 88≈1.7×1078^8\approx1.7\times10^7
  4. 648≈2.8×101464^8\approx2.8\times10^{14}
Show the answer

C. 88≈1.7×1078^8\approx1.7\times10^7

Each of the 8 column variables independently takes one of 8 rows: 88=16,777,2168^8=16{,}777{,}216. 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.

DerivationCounting the leaves of the search tree
  1. nd⋅(n−1)d⋅(n−2)d⋯1⋅d=n! dn leavesnd\cdot(n-1)d\cdot(n-2)d\cdots1\cdot d=n!\,d^n\ \text{leaves}

    Naively, any of the nn variables can get any of dd values at the root, any of the remaining n−1n-1 at the next level, and so on:

  2. d⋅d⋯d⏟n levels=dn\underbrace{d\cdot d\cdots d}_{n\ \text{levels}}=d^n

    But assignment is commutative: {WA=r, NT=g}\{\mathrm{WA}=r,\ \mathrm{NT}=g\} is the same state whichever came first, so every complete assignment sits at n!n! leaves. Branching on a single variable at each node removes the duplicates:

  3. 7!⋅37=5040⋅2187=11,022,480vs.37=21877!\cdot3^7=5040\cdot2187=11{,}022{,}480\qquad\text{vs.}\qquad3^7=2187

    For Australia (n=7n=7, d=3d=3) that is the difference between eleven million leaves and 2,187:

  4. dead end at depth k ⟹ d n−k leaves never generated\text{dead end at depth }k\ \Longrightarrow\ d^{\,n-k}\ \text{leaves never generated}

    Backtracking prunes on top of this: a partial assignment of kk variables that violates a constraint is abandoned at once, discarding all of its completions unseen.

text
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 failure

The 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 nn (plus what it saves to undo inferences), and O(dn)\order{d^n} time in the worst case.

Check your understanding

Why does branching on a single variable at each node lose no solutions?

  1. Because the chosen variable is always the most constrained one
  2. Because an assignment is a set of variable–value pairs, so order is irrelevant: every complete assignment still lies on exactly one path
  3. Because backtracking later revisits the other variable orders
  4. 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 n!−1n!-1 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 X=vX=v: it deletes every value that conflicts with vv 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 ={blue}=\{\text{blue}\} and SA ={blue}=\{\text{blue}\}. They are neighbors, so this is a dead end, but forward checking does not notice.

text
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 revised

AC-3 (Mackworth, 1977). When DiD_i shrinks, every arc pointing into XiX_i is rechecked, because some neighbor's value may just have lost its only support.

DerivationAC-3 runs in O(ed³) time
  1. initial queue: 2e arcs\text{initial queue: } 2e\ \text{arcs}

    Take a binary CSP with nn variables, ee constraints and domains of size at most dd. Each constraint gives two arcs, and all of them start in the queue:

  2. insertions ≤ 2e+∑id deg⁡(Xi)=2e+2ed=O(ed)\text{insertions}\ \le\ 2e+\sum_i d\,\deg(X_i)=2e+2ed=\order{ed}

    An arc (Xk,Xi)(X_k,X_i) is queued again only when DiD_i loses a value, which happens at most dd times. Each such loss queues at most deg⁡(Xi)\deg(X_i) arcs:

  3. one REVISE=O(d2) constraint checks\text{one REVISE}=\order{d^2}\ \text{constraint checks}

    Each REVISE(Xi,Xj)(X_i,X_j) tests every x∈Dix\in D_i against every y∈Djy\in D_j:

  4. O(ed)×O(d2)=O(ed3)\order{ed}\times\order{d^2}=\order{ed^3}

    Multiply. AC-4 (Mohr & Henderson, 1986) brings this down to O(ed2)\order{ed^2}, which is optimal: checking every arc once already costs that much in the worst case.

Check your understanding

WA = red and Q = green, and forward checking has left NT ={blue}=\{\text{blue}\} and SA ={blue}=\{\text{blue}\}. What does AC-3 do?

  1. Nothing: no domain is empty
  2. It assigns blue to both NT and SA
  3. 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
  4. 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 (Xj,Xi)(X_j,X_i) from the unassigned neighbors XjX_j of the variable XiX_i 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: n/cn/c components of cc variables cost (n/c) dc(n/c)\,d^c instead of dnd^n.
  • 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 nn-queens, its running time after the initial placement is roughly independent of nn: 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 (X,D,C)(\mathcal X,\mathcal D,\mathcal C), 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 (dnd^n leaves, not n! dnn!\,d^n) 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 O(ed3)\order{ed^3}, and MAC reruns it after every assignment.
  • Tree-structured CSPs take O(nd2)\order{nd^2}; 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.

Question 1

A binary CSP has nn variables, ee constraints and domains of size dd. What is AC-3's worst-case running time?

  1. O(nd2)\order{nd^2}
  2. O(ed2)\order{ed^2}
  3. O(dn)\order{d^n}
  4. O(ed3)\order{ed^3}
Show the answer

D. O(ed3)\order{ed^3}

Each of the 2e2e arcs re-enters the queue at most dd times, once per value its target can lose, so there are O(ed)\order{ed} revisions, each costing O(d2)\order{d^2}.

Question 2

No region of Australia is colored yet, and MRV breaks ties with the degree heuristic. Which region is assigned first?

  1. Western Australia, the first in the list
  2. South Australia
  3. Tasmania
  4. 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.

Question 3

When does the order in which values are tried make no difference to the total work of backtracking?

  1. When MRV chooses the variables
  2. When the constraint graph is a tree
  3. When every domain has the same size
  4. 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.

Question 4

Which statement about forward checking (FC) and maintaining arc consistency (MAC) is true?

  1. MAC prunes every value FC prunes, and possibly more, at a higher cost per node
  2. FC and MAC always prune exactly the same values
  3. With MAC, backtracking is never needed
  4. 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.

Question 5

A CSP's constraint graph is a tree with n=100n=100 variables and d=10d=10 values each. Roughly how many value-pair checks does the tree algorithm's upward pass need in the worst case?

  1. About 1010010^{100}
  2. About 10410^4
  3. About 10310^3
  4. About 10610^6
Show the answer

B. About 10410^4

One REVISE per edge, n−1=99n-1=99 of them, each comparing up to d2=100d^2=100 value pairs: about 9,9009{,}900 checks. The tree shape turns an exponential problem into a linear one.

Go deeper

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).