--- title: Constraint Satisfaction Problems module: Search moduleNumber: 2 lessonNumber: 9 order: 209 summary: > A constraint satisfaction problem replaces the black-box state with a factored one: variables, domains, and constraints. That structure supports inference before any search runs. This lesson defines the CSP on map coloring, Sudoku, and scheduling, then develops constraint propagation: node and arc consistency, the AC-3 algorithm that makes a whole network arc-consistent, and the way one deleted value cascades across the graph to prune impossible options ahead of search. topics: [Search] sources: - book: AIMA ref: "Ch. 6 — Constraint Satisfaction Problems; §6.1 Defining CSPs" - book: AIMA ref: "§6.2 Constraint Propagation" --- The [search algorithms](/artificial-intelligence/foundations/intelligent-agents) 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.[^aima-intro] 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](/artificial-intelligence/search/csp-search-and-structure). ## Defining a CSP A constraint satisfaction problem has three components, written $X$, $D$, and $C$. > **Definition (Constraint satisfaction problem).** A triple $(X, D, C)$ where > $X = \{X_1, \ldots, X_n\}$ is a set of **variables**; $D = \{D_1, \ldots, D_n\}$ > gives each variable $X_i$ a **domain** $D_i = \{v_1, \ldots, v_k\}$ of allowable > values; and $C$ is a set of **constraints**, each a pair > $\langle \mathit{scope}, \mathit{rel} \rangle$ naming the variables it involves > and the combinations of values they may jointly take. 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, $\langle (X_1, X_2), [(A,B), (B,A)] \rangle$ and $\langle (X_1, X_2), X_1 \ne X_2 \rangle$ 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.[^aima-assign] ### 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, $$ X = \{ WA, NT, Q, NSW, V, SA, T \}, $$ each with domain $D_i = \{red, green, blue\}$. The constraints require adjacent regions to differ, and there are nine adjacencies: $$ C = \{\, SA \ne WA,\; SA \ne NT,\; SA \ne Q,\; SA \ne NSW,\; SA \ne V,\; WA \ne NT,\; NT \ne Q,\; Q \ne NSW,\; NSW \ne V \,\}. $$ Here $SA \ne WA$ abbreviates $\langle (SA, WA),\, SA \ne WA \rangle$. 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. $$ % caption: The map-coloring CSP as a constraint graph. Each node is a region; % each edge is a $\ne$ constraint between neighbors. $SA$ borders five regions, % so it has degree $5$; Tasmania ($T$) touches nothing. \begin{tikzpicture}[>=stealth, font=\small, reg/.style={circle, draw, minimum size=8mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node[reg] (WA) at (0,1.2) {WA}; \node[reg] (NT) at (1.9,2.3) {NT}; \node[reg] (SA) at (2.1,0.4) {SA}; \node[reg] (Q) at (3.8,2.3) {Q}; \node[reg] (NSW) at (4.2,0.7) {NSW}; \node[reg] (V) at (3.3,-0.9) {V}; \node[reg] (T) at (4.6,-1.9) {T}; \draw (WA) -- (NT); \draw (WA) -- (SA); \draw (NT) -- (SA); \draw (NT) -- (Q); \draw[acc, thick] (SA) -- (Q); \draw[acc, thick] (SA) -- (NSW); \draw[acc, thick] (SA) -- (V); \draw (Q) -- (NSW); \draw (NSW) -- (V); \end{tikzpicture} $$ 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.[^aima-map] 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, \ldots, 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.[^aima-sudoku] _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.[^aima-sched] A **disjunctive constraint** — two tasks that share a tool may not overlap — reads $(T_1 + d_1 \le T_2) \lor (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. | Kind | Arity | Example | | --- | --- | --- | | Unary | one variable | $\langle (SA),\, SA \ne green \rangle$ | | Binary | two variables | $SA \ne NSW$ | | Higher-order / global | $n$ variables | $\mathit{Alldiff}(X_1, \ldots, X_k)$ | | Preference (soft) | any | assigning Prof. R the 2 p.m. slot costs 2 | 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.[^aima-var] 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.[^aima-prop] **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. > **Definition (Arc consistency).** A variable $X_i$ is arc-consistent with > respect to $X_j$ if for every value in the current domain $D_i$ there is some > value in $D_j$ that satisfies the binary constraint on the arc $(X_i, X_j)$. > A network is arc-consistent when every variable is arc-consistent with every > other. 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, \ldots, 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.[^aima-kcon] 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. $$ % caption: The consistency ladder. Each rung enforces consistency over one more % variable at a time; higher rungs prune more but cost exponentially more to % establish. Arc consistency (rung 2) is the practical sweet spot. \begin{tikzpicture}[>=stealth, font=\footnotesize, rung/.style={draw, minimum width=52mm, minimum height=6mm, inner sep=2pt, align=left, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[rung] (r1) at (0,0) {1: node consistency (unary, one variable)}; \node[rung, draw=acc, thick] (r2) at (0.5,0.85) {2: arc consistency (binary, pairs)}; \node[rung] (r3) at (1.0,1.7) {3: path consistency (triples)}; \node[rung] (r4) at (1.5,2.55) {k: k-consistency (k-tuples)}; \node[acc, font=\scriptsize, anchor=west, align=left] at (5.1,0.85) {cheap,\\practical}; \node[font=\scriptsize, anchor=west, align=left] at (5.6,2.55) {costly,\\rarely worth it}; \draw[->, thick] (3.2,-0.3) -- (5.3,2.85) node[midway, sloped, above, black, font=\scriptsize] {more pruning}; \end{tikzpicture} $$ **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.[^aima-sudoku] ### 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.[^aima-ac3] ```algorithm caption: $\textsc{AC-3}$ — make a binary CSP arc-consistent, or detect failure input: a binary CSP with components $(X, D, C)$ $\mathit{queue} \gets$ all arcs in the CSP while $\mathit{queue}$ is not empty do $(X_i, X_j) \gets$ remove any arc from $\mathit{queue}$ if $\textsc{Revise}(X_i, X_j)$ then if size of $D_i = 0$ then return false // domain wiped out for each $X_k$ in $\text{Neighbors}(X_i) \setminus \{X_j\}$ do add $(X_k, X_i)$ to $\mathit{queue}$ // recheck arcs into $X_i$ return true ``` ```algorithm caption: $\textsc{Revise}$ — prune $D_i$ against the arc $(X_i, X_j)$ input: variables $X_i$, $X_j$ sharing a binary constraint $\mathit{revised} \gets \textbf{false}$ for each $x$ in $D_i$ do if no value $y$ in $D_j$ lets $(x, y)$ satisfy the constraint then delete $x$ from $D_i$ $\mathit{revised} \gets \textbf{true}$ return $\mathit{revised}$ ``` 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. $$ % caption: Arc consistency on $Y = X^2$ over digit domains, before (top) and after % (bottom). $\textsc{Revise}(X,Y)$ deletes every $x$ whose square is not a digit, % cutting $D_X$ to $\{0,1,2,3\}$; $\textsc{Revise}(Y,X)$ then cuts $D_Y$ to % $\{0,1,4,9\}$. Struck values are pruned; a value survives only if it has a % partner across the arc. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % BEFORE: full domains \node[anchor=east] at (-0.4,3.6) {before}; \node[anchor=east] at (0.9,3.0) {$D_X$:}; \node[anchor=east] at (0.9,2.4) {$D_Y$:}; \foreach \v/\x in {0/0, 1/0.55, 2/1.1, 3/1.65, 4/2.2, 5/2.75, 6/3.3, 7/3.85, 8/4.4, 9/4.95} { \node at (\x+1.2,3.0) {\v}; \node at (\x+1.2,2.4) {\v}; } % arrow between panels \draw[->, acc, very thick] (3.3,1.9) -- (3.3,1.2); \node[acc, anchor=west, font=\scriptsize] at (3.5,1.55) {enforce arc consistency}; % AFTER: pruned domains \node[anchor=east] at (-0.4,0.5) {after}; \node[anchor=east] at (0.9,0.5) {$D_X$:}; \node[anchor=east] at (0.9,-0.1) {$D_Y$:}; % D_X after: keep 0-3, strike 4-9 \foreach \v/\x/\del in {0/0/0, 1/0.55/0, 2/1.1/0, 3/1.65/0, 4/2.2/1, 5/2.75/1, 6/3.3/1, 7/3.85/1, 8/4.4/1, 9/4.95/1} { \ifnum\del=1 \node[red] at (\x+1.2,0.5) {\v}; \draw[red, thick] (\x+1.04,0.34) -- (\x+1.36,0.66); \else \node[acc] at (\x+1.2,0.5) {\v}; \fi } % D_Y after: keep 0,1,4,9; strike 2,3,5,6,7,8 \foreach \v/\x/\del in {0/0/0, 1/0.55/0, 2/1.1/1, 3/1.65/1, 4/2.2/0, 5/2.75/1, 6/3.3/1, 7/3.85/1, 8/4.4/1, 9/4.95/0} { \ifnum\del=1 \node[red] at (\x+1.2,-0.1) {\v}; \draw[red, thick] (\x+1.04,-0.26) -- (\x+1.36,0.06); \else \node[acc] at (\x+1.2,-0.1) {\v}; \fi } \end{tikzpicture} $$ 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(cd^3)$.[^aima-ac3] ### 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. | Step | Arc popped | $\textsc{Revise}$ deletes | New domain | Re-enqueued | | --- | --- | --- | --- | --- | | 1 | $(NT, WA)$ | $R$ from $NT$ | $D_{NT} = \{G, B\}$ | $(SA, NT), (Q, NT)$ | | 2 | $(SA, WA)$ | $R$ from $SA$ | $D_{SA} = \{B\}$ | $(NT, SA), (Q, SA), (NSW, SA), (V, SA)$ | | 3 | $(NT, SA)$ | $B$ from $NT$ | $D_{NT} = \{G\}$ | $(Q, NT)$ | | 4 | $(Q, SA)$ | $B$ from $Q$ | $D_{Q} = \{R, G\}$ | $(NSW, Q)$ | | 5 | $(Q, NT)$ | $G$ from $Q$ | $D_{Q} = \{R\}$ | $(NSW, Q)$ | | 6 | $(NSW, Q)$ | $R$ from $NSW$ | $D_{NSW} = \{G, B\}$ | $(V, NSW)$ | | 7 | $(NSW, SA)$ | $B$ from $NSW$ | $D_{NSW} = \{G\}$ | $(V, NSW)$ | | 8 | $(V, NSW)$ | $G$ from $V$ | $D_{V} = \{R, B\}$ | $(SA, V)$ | 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. $$ % caption: The AC-3 propagation chain from the trace. Enforcing $WA=R$ and $SA \ne % green$ deletes a value from $SA$, whose incoming arcs then delete from $NT$, $Q$, % $NSW$, and $V$ in turn. Each arrow is a re-enqueued arc; the numbers match the % trace steps. \begin{tikzpicture}[>=stealth, font=\footnotesize, reg/.style={circle, draw, minimum size=9mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node[reg, draw=acc, thick] (SA) at (0,0) {SA}; \node[reg] (NT) at (-2.3,1.3) {NT}; \node[reg] (Q) at (2.3,1.3) {Q}; \node[reg] (NSW) at (2.6,-0.9) {NSW}; \node[reg] (V) at (0.1,-2.0) {V}; \node[below=1pt of SA, acc, font=\scriptsize] {del G}; \draw[->, acc, thick] (SA) -- (NT) node[midway, above left, black, font=\scriptsize] {3}; \draw[->, acc, thick] (SA) -- (Q) node[midway, above right, black, font=\scriptsize] {4}; \draw[->, acc, thick] (SA) -- (NSW) node[midway, right, black, font=\scriptsize] {7}; \draw[->, thick] (NT) -- (Q) node[midway, above, black, font=\scriptsize] {5}; \draw[->, thick] (Q) -- (NSW) node[midway, right, black, font=\scriptsize] {6}; \draw[->, thick] (NSW) -- (V) node[midway, below right, black, font=\scriptsize] {8}; \end{tikzpicture} $$ ### Optimal arc-consistency algorithms AC-3's $O(cd^3)$ bound hides wasted work: when an arc $(X_i, X_j)$ is re-examined, $\textsc{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(cd^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(cd^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.[^acopt] 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](/artificial-intelligence/search/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. [^aima-intro]: **Russell & Norvig**, _AIMA_, Ch. 6 — introduction: the factored representation of a state as variables with values, versus the atomic black-box states of Chapters 3–4, and the payoff of eliminating variable/value combinations that violate constraints. [^aima-assign]: **Russell & Norvig**, _AIMA_, §6.1 — Defining Constraint Satisfaction Problems: the $(X, D, C)$ triple, and the assignment / consistent / complete / partial / solution vocabulary. [^aima-map]: **Russell & Norvig**, _AIMA_, §6.1.1 — Example problem: Map coloring: the Australia CSP, its constraint graph, and the $3^5 \to 2^5$ reduction from propagating a single choice. [^aima-sudoku]: **Russell & Norvig**, _AIMA_, §6.2.6 — Sudoku example: 81 variables, singleton domains for givens, and 27 _Alldiff_ constraints, one per row, column, and box. [^aima-sched]: **Russell & Norvig**, _AIMA_, §6.1.2 — Example problem: Job-shop scheduling: tasks as start-time variables, precedence constraints $T_1 + d_1 \le T_2$, and disjunctive constraints for shared resources. [^aima-var]: **Russell & Norvig**, _AIMA_, §6.1.3 — Variations on the CSP formalism: unary/binary/global constraints; discrete finite, infinite, and continuous domains; constraint languages; preference constraints and constraint optimization. [^aima-prop]: **Russell & Norvig**, _AIMA_, §6.2 — Constraint Propagation: search versus inference, local consistency, and node consistency. [^aima-kcon]: **Russell & Norvig**, _AIMA_, §6.2.3–6.2.4 — Path consistency and $k$-consistency: two-color Australia defeats arc consistency; path consistency reasons over triples; $k$-consistency generalizes the ladder. [^aima-ac3]: **Russell & Norvig**, _AIMA_, §6.2.2 — Arc consistency and the AC-3 algorithm (Figure 6.3): the queue of arcs, re-adding incoming arcs after a revision, and the $O(cd^3)$ worst-case bound. [^acopt]: **R. Mohr & T. Henderson**, "Arc and Path Consistency Revisited," _Artificial Intelligence_ 28(2), 1986 — the optimal $O(cd^2)$ AC-4 algorithm. **C. Bessière & J.-C. Régin**, "Refining the Basic Constraint Propagation Algorithm," _IJCAI_ 2001 — AC-2001/AC-3.1 achieving $O(cd^2)$ with lighter bookkeeping.