Arc Consistency

A constraint problem is a set of variables, a domain for each, and constraints restricting combinations. Search assigns values and checks them. Propagation does something different: it looks at the domains and removes values that cannot possibly participate in a solution, which shrinks the problem itself rather than exploring it.

An arc from X to Y is consistent when every value remaining in X has at least one value in Y that satisfies the constraint between them. Making it consistent means deleting the unsupported values of X. The subtlety is that this can break arcs that were already consistent, because a value in some third variable Z may have been relying on a value of X that has now gone. The standard algorithm, AC-3, handles that with a queue: whenever a domain shrinks, every arc pointing into that variable goes back on the queue.

The payoff is a conclusion no local check can reach. If a domain empties, no solution exists below this point in the search, and the branch can be abandoned immediately. That is why propagation is interleaved with search rather than run once at the start, and why the combination beats either alone.

What it cannot do is decide the problem. Arc consistency only ever looks at pairs, so a contradiction that emerges only from three or more variables together survives it. An arc-consistent problem may still be unsolvable, and stronger and more expensive notions - path consistency, k-consistency - exist precisely to see further at a higher price.

Colour the seven regions of Australia with three colours so that neighbours differ, and set Western Australia to red and Queensland to green. Nothing is violated: the two are not adjacent, and a constraint check finds no fault.

Propagation sees further. Northern Territory borders both, so it loses red and green and is left with blue alone; South Australia borders both as well and is left with blue alone too. But Northern Territory and South Australia border each other, so the arc between them removes blue from South Australia and empties its domain. There is no solution below this point.

Brute force over all 3^7 = 2,187 assignments confirms it: that partial assignment has exactly zero completions, out of the 18 the problem has in total. Forward checking, which only prunes the neighbours of a variable as it is assigned, leaves both domains at a single value, sees nothing wrong, and keeps searching.