Constraint Satisfaction Problems

The search algorithms of the previous lessons treat each state as atomic — a black box the algorithm can test for goalhood and expand, but never look inside. A constraint satisfaction problem opens the box: it uses a factored representation, where a state is a set of variables, each holding a value, and the problem is solved when every variable has a value that satisfies all the constraints.¹ Once the algorithm can see a state's internal structure, it can do something a generic searcher cannot — reason about why a partial state is doomed and discard whole regions of the space at once, using general-purpose machinery rather than a hand-built heuristic per problem.

This lesson defines the CSP and shows how many different-looking problems share its shape, then develops constraint propagation: using the constraints to shrink the variables' options before any search runs. The search itself — backtracking with CSP-specific heuristics — and the structural tricks that make whole classes of CSP easy are the subject of the companion lesson, CSP Search and Structure.

Defining a CSP

A constraint satisfaction problem has three components, written $X$, $D$, and $C$.

A relation can be listed explicitly (every tuple that satisfies it) or given abstractly as a test — for two variables with domain $\{A,B\}$ that must differ, $⟨(X_1,X_2),[(A,B),(B,A)]⟩$ and $⟨(X_1,X_2),X_1\ne X_2⟩$ say the same thing. To search a CSP we define its state space through assignments. An assignment gives values to some or all variables; it is consistent if it violates no constraint; a complete assignment names every variable; and a solution is a consistent, complete assignment. A partial assignment leaves some variables unset — the states backtracking search moves through.²

Map coloring

The canonical example colors a map of Australia. Each region must be red, green, or blue so that no two neighboring regions share a color. The variables are the seven regions,

each with domain $D_i=\{red,green,blue\}$. The constraints require adjacent regions to differ, and there are nine adjacencies:

Here $SA\ne WA$ abbreviates $⟨(SA,WA),SA\ne WA⟩$. One of the many solutions is $\{WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=red\}$. It helps to picture a CSP as a constraint graph: one node per variable, and an edge between any two variables that share a constraint.

Recasting a problem this way makes the solver faster. Choose $SA=blue$ and every one of its five neighbors instantly loses $blue$ as an option. A blind state-space search over those five neighbors would face $3^5=243$ combinations; propagating the one choice leaves $2^5=32$, an 87% cut — and it costs nothing beyond reading the graph.³ More generally, the moment a partial assignment breaks a constraint, we know it can never extend to a solution, and we see exactly which variables to blame.

Other problems, same shape

Sudoku is a CSP with 81 variables, one per square, named $A1$ through $I9$. An empty square has domain $\{1,\dots ,9\}$; a pre-filled one has a singleton domain. The rules are 27 Alldiff constraints — one for each row, column, and $3\times 3$ box — asserting that the nine variables in that unit take distinct values.⁴ Alldiff is a global constraint: it relates an arbitrary number of variables, and can be enforced by a special-purpose algorithm more efficiently than the equivalent pile of pairwise $\ne$ constraints.

Job-shop scheduling models the assembly of a product as tasks with start times. Each task is a variable whose value is the minute it begins; a precedence constraint $T_1+d_1\le T_2$ says task $T_1$, which takes duration $d_1$, must finish before $T_2$ starts.⁵ A disjunctive constraint — two tasks that share a tool may not overlap — reads $(T_1+d_1\le T_2)\vee (T_2+d_2\le T_1)$. Real schedulers run CSPs of this form with thousands of variables.

The variety hints at a taxonomy of constraint types.

Domains vary too: finite (map colors, digits), infinite discrete (integer start times with no deadline, needing a constraint language rather than an enumerated relation), and continuous (the best-known continuous CSPs are linear programs). The preference constraints of the last row soften the formalism into a constraint optimization problem, where violating a constraint costs points rather than ruling a solution out; every constraint we treat below is absolute.⁶ Any higher-order constraint can be rewritten with auxiliary variables as a set of binary ones, so the algorithms that follow assume binary CSPs without loss of generality.

Constraint propagation

A generic searcher has one move: search. A CSP solver has two — it can search, or it can infer, using the constraints to shrink domains before or during search. If choosing a value somewhere rules out values elsewhere, those values can be deleted before search ever reaches them. Inference works through local consistency: enforce consistency in one corner of the constraint graph, and inconsistent values get eliminated throughout it. Sometimes propagation alone solves the problem; often it makes the remaining search much cheaper.⁷

Node consistency. A variable is node-consistent when every value in its domain satisfies its unary constraints. If South Australians dislike green, we make $SA$ node-consistent by deleting $green$, leaving $\{red,blue\}$. Enforcing node consistency once removes all unary constraints, which is why solvers can assume they've been discharged.

Arc consistency is the central algorithm for binary CSPs, so we state it carefully.

In plain terms: a value survives in $D_i$ only if it has at least one legal partner across the arc. Take the constraint $Y=X^2$ with both domains the digits $\{0,\dots ,9\}$. Making $X$ arc-consistent with $Y$ deletes every $x$ whose square is not a digit, reducing $D_X$ to $\{0,1,2,3\}$; making $Y$ arc-consistent with $X$ leaves $D_Y=\{0,1,4,9\}$. Arc consistency can go far: on Sudoku, repeatedly enforcing it drives many domains to a single value and can solve easy puzzles outright. But it has limits — on a two-color map of Australia every variable is already arc-consistent (each value has a differing partner across the arc), yet no solution exists. Catching that needs path consistency, which tightens triples of variables by checking whether an assignment to two of them can be extended to a third. Both are special cases of $k$-consistency: 1-consistency is node consistency, 2-consistency is arc consistency, 3-consistency is path consistency.⁸ A CSP is strongly $k$-consistent if it is $j$-consistent for every $j\le k$; a strongly $n$-consistent CSP on $n$ variables can be solved with no backtracking at all, by assigning variables in order and always finding a legal value. The catch is cost: establishing $k$-consistency is worst-case exponential in $k$ in both time and space, so in practice solvers stop at arc consistency (fast, cheap) and reach for path consistency only when it clearly pays.

Sudoku shows both ends of this ladder in action. Enforcing arc consistency across the 27 Alldiff constraints solves the easiest puzzles outright, driving every domain to a singleton. Harder puzzles resist it, and human solvers reach for richer inference with names like naked triples: if three squares in a unit hold domains that are all subsets of the same three digits — say $\{1,8\}$, $\{3,8\}$, $\{1,3,8\}$ — then those three digits are locked into those three squares, so they can be deleted from every other square in the unit. This is nothing but a special-purpose way to enforce consistency of the Alldiff constraint, and it says nothing about Sudoku specifically; the same reasoning applies to any global Alldiff. The lesson generalizes: define a problem in constraint terms and the general machinery — arc consistency, path consistency, global-constraint propagators — takes over, with no problem-specific solver to write.⁴

The AC-3 algorithm

The standard way to make an entire network arc-consistent is AC-3. It keeps a queue of arcs to examine. Pop an arc $(X_i,X_j)$ and make $X_i$ arc-consistent with $X_j$; if that deletes anything from $D_i$, then every arc $(X_k,X_i)$ into $X_i$ from a neighbor $X_k$ goes back on the queue, because a change in $D_i$ might now permit deletions in $D_k$. If any domain is emptied, the CSP has no solution and AC-3 reports failure at once. Otherwise it stops when the queue drains, leaving a CSP with the same solutions but smaller domains.⁹

The pruning cascades. Consider $Y=X^2$ once more: the figure traces how deleting a value from one domain sends its incoming arcs back to the queue, so the reduction ripples outward until nothing more can be removed.

AC-3's cost is bounded cleanly. With $n$ variables, at most $d$ values each, and $c$ binary arcs, each arc $(X_k,X_i)$ enters the queue at most $d$ times (once per possible deletion in $D_i$), and checking an arc costs $O(d^2)$, for a worst case of $O(c{d}^3)$.⁹

A worked AC-3 trace

The $Y=X^2$ example prunes but never cascades — each domain is revised once and the queue drains. To see AC-3 propagate, seed the Australia map with two unary constraints and watch one deletion trigger the next. Suppose Western Australia must be $red$ (a fixed border color) and South Australia dislikes $green$. Node consistency discharges the unary constraints first: $D_{WA}=\{R\}$ and $D_{SA}=\{R,B\}$, every other domain still $\{R,G,B\}$. Now run AC-3. The table below follows the queue arc by arc; only arcs that revise a domain are shown, and each successful revision re-enqueues the neighbors pointing into the shrunken variable.

Two unary facts have collapsed almost the entire map: after step 8 the domains are $WA=\{R\}$, $NT=\{G\}$, $SA=\{B\}$, $Q=\{R\}$, $NSW=\{G\}$, with $V=\{R,B\}$ and $T=\{R,G,B\}$ still open. Arc consistency did not fully solve the CSP — $V$ and $T$ retain choices — but it fixed five of seven variables without a single search step, and the remaining tree ($V$, then $T$) has no way to fail. That is the point of propagating before searching: the deletion of $green$ from $SA$ in step 2 forced the deletion in $NT$ in step 3, which forced $Q$ in step 5, which forced $NSW$ in step 7, a four-hop chain from one unary constraint.

Optimal arc-consistency algorithms

AC-3's $O(c{d}^3)$ bound hides wasted work: when an arc $(X_i,X_j)$ is re-examined, $\text{Revise}$ rescans all of $D_i$ even though only the recent deletion in $D_j$ could have changed anything. AC-4 (Mohr and Henderson, 1986) removes that waste by precomputing, for every value $x\in D_i$, a support count: the number of values in $D_j$ compatible with $x$. Deleting a value $y$ from $D_j$ decrements the counts of exactly the values $x$ it supported; a count hitting zero deletes $x$ and cascades. This reaches the optimal $O(c{d}^2)$ worst case, but its up-front bookkeeping makes it slower than AC-3 on easy instances. AC-2001 (Bessière and Régin, 2001) attains the same $O(c{d}^2)$ bound while keeping only a pointer to the first surviving support per value, and beats AC-4 in practice by not maintaining the full count structure. AIMA presents AC-3 because it is simple and fast enough for the problems in the chapter; production solvers use the AC-2001-style variants.¹⁰

Propagation prunes, but it rarely finishes the job on its own — $V$ and $T$ above still have choices to make. Search handles the rest, and the CSP's structure pays off a second time there. This continues in CSP Search and Structure, which develops backtracking search with the MRV, degree, and least-constraining-value heuristics, and then shows how the shape of the constraint graph controls how hard the whole problem is.