Constraint Satisfaction and Propagation

Classical search treats a problem as a black box: an initial state, some actions, a goal test. The solver can tell whether it has arrived, but never why a state is bad, so all its intelligence has to arrive from outside as a hand-written heuristic. Constraint satisfaction opens the box, and the payoff is that a single solver with no domain knowledge can beat bespoke search on problems with nothing in common.

A. The standard form

A CSP is a set of variables, a domain of permitted values for each, and constraints restricting which combinations may occur together. An assignment is consistent if it violates nothing, complete if every variable has a value, and a solution if both.

Colour the seven regions of Australia with three colours so that no two adjacent regions match. Seven variables, domain $\{\text{red}, \text{green}, \text{blue}\}$, and nine constraints, one per shared border. Tasmania is an island and appears in none of them.

The binary constraints induce a constraint graph, and its most useful readout is degree, the number of constraints a variable takes part in:

$$\begin{array}{ll} \mathrm{SA} & 5 \\ \mathrm{NT},\ \mathrm{Q},\ \mathrm{NSW} & 3 \\ \mathrm{WA},\ \mathrm{V} & 2 \\ \mathrm{T} & 0 \end{array}$$

South Australia touches every mainland region, so assigning it constrains five others at once. Tasmania constrains nothing, which already tells you the 18 solutions are six mainland colourings times three free choices for Tasmania.

The same form swallows unrelated problems. Scheduling becomes one variable per task valued by start time, with precedence constraints $T_1 + d_1 \le T_2$ and a deadline as a restriction on every domain. Sudoku becomes 81 variables with 27 all-different constraints. None needs its own solver.

B. Commutativity, for free

A naive tree treats "assign WA then NT" as different from "assign NT then WA". Count its leaves: $n!$ orderings times $d^n$ combinations,

$$7! \times 3^7 = 5{,}040 \times 2{,}187 = 11{,}022{,}480 .$$

But assignment is commutative - any order reaches the same partial assignment - so the ordering carries no information and a solver may fix one variable per level. That gives $d^n = 2{,}187$ leaves, a factor of 5,040 smaller, with nothing given up. It is not a heuristic. It is a redundancy the naive formulation should never have had.

C. Propagation, and what it can prove

Before guessing, delete values that cannot appear in any solution. A variable is arc-consistent with respect to another when every value in its domain has some partner in the other's domain satisfying their constraint. The AC-3 algorithm enforces this everywhere: keep a queue of arcs, revise each by deleting unsupported values, and whenever a domain shrinks, push back the arcs of that variable's neighbours, because their support may have vanished too.

Run it on the untouched Australia problem and it makes zero revisions. Every region still has three colours, so whatever value you consider, the neighbour has two others and nothing can be deleted. Propagation is not a solver; it exploits asymmetries between domains, and at the start there are none. What creates them is an assignment.

So make two. Set $\mathrm{WA} = \text{red}$ and $\mathrm{Q} = \text{green}$.

Forward checking, the cheapest useful inference, deletes the assigned value from each unassigned neighbour. It leaves $\mathrm{NT} = \{\text{blue}\}$ and $\mathrm{SA} = \{\text{blue}\}$ - two singletons, nothing empty - and the search continues.

Arc consistency goes one step further. NT is now a singleton; SA is adjacent to NT; SA's only remaining value is blue and so is NT's, so blue loses its support and $D_{\mathrm{SA}}$ empties. The branch is dead, and AC-3 says so before another assignment is made.

It really is dead. Brute force over the remaining five regions finds zero completions, for a reason short enough to check by hand: NT and SA must both avoid red and green, so both are forced to blue, and they border each other.

The difference is reach. Forward checking propagates outward from the variable just assigned and stops, so it never compares NT with SA. AC-3 propagates until nothing changes.

Propagation is sound: it never deletes a value that could appear in a solution. It is not complete. Try to two-colour Australia and AC-3 reports the problem arc-consistent while deleting nothing, yet there are zero solutions. Arc consistency inspects two variables at a time, and no pair is contradictory; what is contradictory is a three-region cycle needing three colours. Seeing that takes path consistency, and full $k$-consistency costs time and space exponential in $k$. Arc consistency is the point where inference is still cheap enough to run at every node.

D. Search, and the heuristic that does nothing

What closes the gap is backtracking: depth-first assignment, backing up when a variable has no legal value. Three standard heuristics steer it.

Minimum remaining values picks the variable with fewest values left. It is fail-first: it heads for the variable most likely to fail, so dead ends surface near the top of the tree. Degree breaks its ties by preferring the variable in the most constraints - South Australia, at the start of the map problem, where every domain still has three values. Least constraining value picks the value ruling out fewest choices for neighbours, which is fail-last.

The asymmetry is deliberate. Every variable must eventually be assigned, so exposing a doomed one early prunes cheaply; but only one value has to work, so try the most permissive first. Were you enumerating all solutions, value ordering would stop mattering.

Now the measurement. Take $N$-queens as a CSP, one variable per column valued by row, and count assignments made (a value that clashes with a queen already placed is rejected without counting; count those too and plain backtracking tries 876 at 8 queens):

$$\begin{array}{r|rrrr} n & \text{plain} & \text{MRV} & \text{FC} & \text{MRV + FC} \\ \hline 8 & 113 & 113 & 88 & 75 \\ 16 & 10{,}052 & 10{,}052 & 7{,}560 & 44 \\ 24 & 411{,}608 & 411{,}608 & 286{,}963 & 43 \end{array}$$

Look at the second column. Minimum remaining values, on its own, changes nothing - not approximately, exactly nothing, at every size. Once seen the reason is obvious: MRV ranks variables by remaining domain size, and plain backtracking never deletes anything. It checks a candidate against the current assignment and moves on. Every unassigned variable ties at the full domain size, so MRV has no information to act on and, breaking ties by column order, picks exactly what plain backtracking picks.

Forward checking alone saves a quarter or so: 22% at 8 queens, 30% at 24. Together they take 411,608 assignments down to 43.

That table is the kind of claim worth checking rather than believing, so the figure below runs the search instead of quoting it. Switch to MRV and the count does not move; switch at any board size and it still does not move. Then switch to the pair, drag to 16, and watch 10,052 assignments become 44. The slider stops there because the last row, 24 queens, is 411,608 assignments and that is real arithmetic rather than a redraw.

Where this leaves you

Describing a problem properly is not paperwork; it is what lets a solver reason instead of guess. Commutativity removes a factor of $n!$ before anything runs. Propagation deletes what cannot work and sometimes kills a branch outright, while being honest that passing it proves nothing. And the famous ordering heuristics are not tricks in their own right: MRV is a consumer of inference, worth exactly nothing until something else is shrinking domains for it to read. The training path Constraint Satisfaction works each of these by hand and in code.