Constraint Satisfaction Problem

A constraint satisfaction problem replaces the black-box view of search - an initial state, an action function and a goal test - with an explicit description of what makes a state good or bad. Variables carry the choices, domains carry the options, and constraints record which combinations are permitted. An assignment is consistent when it violates no constraint, complete when every variable has a value, and a solution when it is both. Because the description is standardised, a solver needs nothing problem-specific: it can inspect the constraints themselves to decide what to try next and what to rule out.

The binary constraints induce a constraint graph, one node per variable and one edge per constraint, and the shape of that graph is the solver’s map of the problem. The degree of a variable, the number of constraints it participates in, predicts how much assigning it will restrict everything else. Russell and Norvig’s standard example colours the seven regions of Australia with three colours under nine adjacency constraints; South Australia has degree five and Tasmania, an island, has degree zero, so Tasmania’s colour is free and the eighteen solutions fall into six mainland colourings times three.

Two ideas make the form tractable in practice. The first is commutativity: reaching a partial assignment by one order of assignments is the same as reaching it by any other, so the order carries no information and a solver may fix one variable per level of its tree. For seven variables and three values that turns 7! × 3⁷ leaves into 3⁷, a factor of 5,040 for free. The second is propagation: before and during search, values with no possible partner can be deleted outright. Arc consistency, enforced by the AC-3 algorithm, makes every ordered pair of variables consistent in time polynomial in the problem size.

Propagation is sound but incomplete. It never deletes a value that could appear in a solution, yet a problem can pass arc consistency and still have none, because arc consistency inspects only two variables at a time and cannot see a contradiction that requires three. What closes the gap is backtracking search, and what makes that search fast is the pairing of inference with ordering heuristics: minimum remaining values chooses the variable closest to failing, degree breaks its ties, and least-constraining-value picks the value that leaves neighbours the most room. The pairing matters more than either half, since a variable-ordering heuristic that reads domain sizes does nothing at all unless something is shrinking domains.

Colouring Australia uses seven variables with domain {red, green, blue} and nine inequality constraints, one per shared border. Running AC-3 on the untouched problem makes zero revisions: every region still has three colours, so no value can be deleted and propagation has nothing to work with until an assignment creates an asymmetry.

Set Western Australia to red and Queensland to green and the branch is already dead, though only one method notices. Forward checking leaves Northern Territory and South Australia each holding the single value blue and continues; full arc consistency propagates that singleton one step further, finds the two regions are adjacent, empties South Australia’s domain and reports failure. Brute force over the remaining five regions confirms there are zero completions.

Measuring N-queens shows why heuristics are usually mispresented. At n = 24, plain backtracking tries 411,608 assignments; adding minimum remaining values alone tries exactly the same number, because nothing is deleting values and every domain ties. Forward checking alone brings it to 286,963, and the two together to 43.