Constraint satisfaction

You are colouring a map of Australia so that no two neighbouring states share a colour. You are filling in a Sudoku grid so that every row, column and box holds each digit once. You are drawing up an exam timetable so that no student sits two papers at the same time. These puzzles feel wildly different — a map, a grid, a calendar — yet a single, elegant framework captures all of them: constraint satisfaction.

The trick is to stop thinking about the goal as some far-off state you must search toward, and start thinking about the structure of the problem. A constraint satisfaction problem (CSP) is described by just three ingredients, and once you have named them, a family of powerful algorithms comes for free.

A CSP consists of three parts:

a set of variables X_1, X_2, \dots, X_n;
a domain D_i for each variable — the finite set of values it may take;
a set of constraints that restrict which combinations of values are allowed.

A solution is a complete assignment (every variable has a value) that is consistent (every constraint is satisfied).

Contrast this with the generic search you met earlier: there, a state was an opaque black box and you only knew whether it was the goal. A CSP is a factored representation — the state is split into named variables — and that visible structure is exactly what lets the solver be clever.

Map colouring: the model problem

Take the classic: colour the regions of a map with three colours so that no two adjacent regions match. As a CSP this is almost trivially direct:

Variables — one per region.
Domains — each region may be red, green or blue.
Constraints — for every pair of adjacent regions A and B: A \neq B.

A constraint that mentions two variables (like A \neq B) is called a binary constraint, and a CSP built entirely from binary constraints has a lovely picture: the constraint graph. Draw one node per variable and one edge per binary constraint. Now the whole problem is a graph, and colouring the map is literally graph colouring. Step through a valid three-colouring below and watch each choice respect its neighbours:

Every edge in that picture is a promise: my two endpoints must differ. The solver's whole job is to find one value per node that keeps every promise at once.

Backtracking search: try, check, back up

How do we actually find a consistent assignment? The workhorse is backtracking search, and it is nothing more than depth-first search over partial assignments:

pick an unassigned variable;
try a value from its domain that is consistent with everything assigned so far;
recurse to the next variable;
if no value works, back up — undo the last choice and try a different one.

Because the order in which you assign variables never changes the final set of solutions, you may fix one variable at each level rather than branching on all of them — which keeps the tree far smaller than blind search would. Here is a complete backtracking three-colourer for a small map. Press Run:

// A small map as an adjacency list. Each region lists the regions it touches. const map: Record<string, string[]> = { WA: ["NT", "SA"], NT: ["WA", "SA", "Q"], SA: ["WA", "NT", "Q", "NSW", "V"], Q: ["NT", "SA", "NSW"], NSW: ["SA", "Q", "V"], V: ["SA", "NSW"], }; const regions = Object.keys(map); const colours = ["Red", "Green", "Blue"]; // the domain (plain data, not figure colours) // Is giving `region` this colour consistent with what we've assigned so far? function ok(region: string, colour: string, asn: Record<string, string>): boolean { return map[region].every((nbr) => asn[nbr] !== colour); // neighbours must DIFFER } // Depth-first backtracking: assign one region at a time. function solve(i: number, asn: Record<string, string>): Record<string, string> | null { if (i === regions.length) return asn; // all assigned → a solution const region = regions[i]; for (const colour of colours) { if (ok(region, colour, asn)) { asn[region] = colour; // try it const result = solve(i + 1, asn); if (result) return result; // success bubbles up delete asn[region]; // else BACK UP and try the next colour } } return null; // no colour worked here → fail upward } const solution = solve(0, {}); if (solution) { for (const r of regions) console.log(r.padEnd(4), "=", solution[r]); } else { console.log("No 3-colouring exists."); }

That delete asn[region] line is the backtrack: when a branch dead-ends we quietly forget the last choice and let the loop try the next colour. Nothing more mysterious than that.

Choosing well: ordering heuristics

Plain backtracking works, but the order in which it picks variables and values makes an enormous difference to how much of the tree it explores. Three cheap, famous heuristics do most of the heavy lifting:

Minimum Remaining Values (MRV) — always assign the variable with the fewest legal values left. Tackle the most-constrained variable first: if it is going to fail, fail now, before wasting effort elsewhere.
Degree heuristic — a tie-breaker for MRV: among equally constrained variables, pick the one involved in the most constraints on other unassigned variables (the highest-degree node in the constraint graph).
Least Constraining Value — once a variable is chosen, try the value that rules out the fewest choices for its neighbours, leaving yourself the most room to succeed.

Notice the pleasing asymmetry: pick the most constrained variable, but the least constraining value. You want to hit trouble early when choosing what to work on, but keep your options open when choosing how.

It sounds backwards — surely you'd tackle the easy variables first? But think about where the tree wastes its time. If a variable has only one legal value left, guessing it now is almost free and might immediately expose a contradiction, pruning a whole doomed subtree before you build it. Leaving it for last means you might colour dozens of other regions perfectly, only to discover at the very bottom that this one variable was impossible all along — and then unwind all that work. MRV's motto is "fail first": find the dead ends while the branch is still cheap to abandon. In practice MRV can shrink the search by orders of magnitude on hard instances.

Looking ahead: inference

Heuristics choose better; inference goes further and prunes the search before it happens, by reasoning about what an assignment forces. Two levels are standard.

Forward checking. The moment you assign a variable, look at each unassigned neighbour and delete from its domain any value the new assignment rules out. If some neighbour's domain goes empty, you know instantly this branch is doomed — so you backtrack immediately, long before a naive search would have noticed.

Arc consistency (AC-3). This is forward checking taken to its logical conclusion. Think of each binary constraint as two directed arcs. An arc X \to Y is consistent when every value in X's domain has some compatible value in Y's domain. If a value of X has no partner, it can never appear in a solution, so we delete it. But pruning X may break an arc Z \to X that was fine before — so we re-queue all arcs pointing into X and keep going until nothing changes.

Put every arc X \to Y of the constraint graph into a queue.
Pop an arc X \to Y and revise it: remove from D_X every value with no consistent partner in D_Y.
If D_X changed, push every arc Z \to X (for neighbours Z \neq Y) back onto the queue.
If any domain becomes empty, the CSP has no solution. Stop when the queue is empty.

Making a CSP arc-consistent does not solve it. AC-3 only removes values that are provably impossible — those with no partner across a single arc. It can finish with every domain still non-empty and yet no complete consistent assignment existing, because a contradiction can hide in a combination of three or more variables that no single arc can see. So arc consistency is a pre-processor and pruner, not a solver: you almost always still need backtracking search on top of it. (The one clean exception is a tree-structured constraint graph — see below.)

A second classic slip: in graph colouring a constraint edge means the two endpoints must differ, not match. It is easy to read an edge as "these are connected, so link their colours" — but the constraint is A \neq B. Edges are separations, not equalities.

Backtracking is exponential in the worst case, but structure can rescue you. If the constraint graph is a tree — no cycles — the CSP can be solved in linear time: pick any node as the root, make every arc consistent from the leaves upward in one sweep, and then a single forward pass assigns every variable with no backtracking ever needed. This is the deep payoff of the CSP framework over generic search: because the structure is visible as a graph, algorithms can exploit it. Real problems are rarely perfect trees, but techniques like cutset conditioning try to chop a graph down to one — trading a small brute-forced core for a tree that then falls in linear time.