Modelling a Problem as Constraints

The search path treated a problem as a black box: an initial state, a set of actions, a goal test. That works, but the solver learns nothing about why a state is bad. A constraint satisfaction problem opens the box. State the problem in a standard form and a general solver can reason about its structure without knowing what it is about.

The standard form

A CSP is three things.

• A set of variables $X_1, \dots, X_n$.
• A domain $D_i$ for each, the values it may take.
• A set of constraints, each restricting the values some subset of variables may take simultaneously.

An assignment gives values to some or all variables. It is consistent if it violates no constraint, complete if every variable has a value, and a solution if it is both.

The example: colouring a map

Colour each region of Australia so that no two adjacent regions share a colour. Seven variables - Western Australia, Northern Territory, Queensland, New South Wales, Victoria, South Australia and Tasmania - each with the domain $\{\text{red}, \text{green}, \text{blue}\}$, and one constraint per shared border:

$$\mathrm{WA} \neq \mathrm{NT},\quad \mathrm{WA} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{Q},\quad \mathrm{SA} \neq \mathrm{Q},$$ $$\mathrm{SA} \neq \mathrm{NSW},\quad \mathrm{SA} \neq \mathrm{V},\quad \mathrm{Q} \neq \mathrm{NSW},\quad \mathrm{NSW} \neq \mathrm{V} .$$

Nine constraints. Tasmania is an island, so it appears in none of them.

The constraint graph

Draw one node per variable and one edge per binary constraint and you have the constraint graph. Its shape is the solver's only map of the problem, and the most useful thing to read off it 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 borders every mainland region. Choosing its colour immediately restricts five other variables, which is why the third lesson assigns high-degree variables early. Tasmania restricts nothing, so its colour is free: that alone tells you the solutions come in groups of three.

There are 18 proper colourings in total, six distinct mainland colourings times three choices for Tasmania.

Colour it yourself below, and watch the second read-out rather than the first. It counts the proper colourings that still extend what you have assigned, and it corrects two readings of the paragraph above.

Fixing any one region leaves exactly six completions. South Australia with five borders, Tasmania with none: six either way, because the three colours are interchangeable and so every region takes every colour in a third of the solutions. High degree buys less search, not fewer answers. That is a weaker claim than it sounds, and it is the one the heuristics lesson actually needs.

Then press the quiet dead end. Western Australia red with Queensland green breaks no constraint at all, and has zero completions: Northern Territory and South Australia are each left needing blue, and they border each other. A consistent partial assignment need not be extendable. Nothing in the standard form notices, which is exactly why the next lesson exists.

Commutativity, and why it is worth 5,040

A naive search would treat "assign WA, then NT" and "assign NT, then WA" as different branches. Count the leaves of that tree: $n!$ orderings times $d^n$ value combinations,

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

But CSPs are commutative: applying a set of assignments in any order reaches the same partial assignment. So the order carries no information, and a solver may fix one variable per level of the tree. The leaf count becomes

$$d^n = 3^7 = 2{,}187 ,$$

a factor of $5{,}040$ smaller, and nothing has been given up. This is not a heuristic or an approximation; it is a redundancy in the naive formulation that should never have been there. Every algorithm in this path assumes it.

The same form, other problems

The point of a standard form is that unrelated problems land in it.

• Scheduling. One variable per task, valued by its start time. A precedence constraint that task $T_1$ of duration $d_1$ finishes before $T_2$ starts is $T_1 + d_1 \le T_2$. A deadline is a restriction on every domain. A shared tool becomes a disjunctive constraint: either $A + 10 \le B$ or $B + 10 \le A$.
• Sudoku. Eighty-one variables, one per square, with domain $\{1, \dots, 9\}$ and singleton domains for the givens. Twenty-seven all-different constraints, one per row, column and box.
• Eight queens. One variable per column, valued by row, with constraints forbidding two queens on a row or diagonal.

None of these needs a bespoke solver. The same code applies to all three because the reasoning it does - shrinking domains, choosing which variable to try next - is driven by the constraints, not by the subject matter.

The form is standard; the difficulty is not. Constraint satisfaction is NP-complete in general, and writing a problem in this form does not make it easy. What it buys is that all the cleverness can live in one solver instead of being reinvented per problem.

Beyond finite domains

Domains need not be small or even finite. A discrete domain can be infinite, like the integers, in which case constraints can no longer be listed as allowed pairs and a constraint language is needed to express $T_1 + d_1 \le T_2$ directly. Linear constraints on integers have specialised solvers; general nonlinear constraints on integers have none, and cannot, since no algorithm for them exists.

Before the quiz

Be able to write a problem as variables, domains and constraints, draw the constraint graph and read degree from it, explain what commutativity removes and what it is worth here, and recognise the same form in scheduling and Sudoku.