CSPs and Map Colouring

Colour a map so that no two neighbouring regions share a colour. It sounds like a puzzle for a rainy afternoon, and it is the standard first example of a constraint satisfaction problem, because the same machinery timetables exams, allocates rooms and fills in Sudoku grids. This note follows a backtracking search as it colours a map, and the two small ideas that make it fast.

The idea

A constraint satisfaction problem (CSP) has three parts: variables, a domain of possible values for each, and constraints on which combinations are allowed. In map colouring the variables are regions, the domain is the set of colours, and every shared border is a constraint that says the two sides must differ. A solution gives every variable a value without breaking any constraint. The Artificial Intelligence topic places CSPs beside search and logic.

The textbook map is mainland Australia plus Tasmania, with three colours. South Australia borders five others, so it is the hardest region to place. Tasmania borders nobody, so it can take any colour at any time. The usual version leaves out the ACT, and adding it changes nothing, because it only touches New South Wales.

Backtracking search colours one region at a time. When a region has no legal colour left, it undoes the most recent choice and tries that region's next colour. It is depth-first search over partial colourings, and it never builds the full tree of every possible colouring because it abandons a branch at the first clash.

Two ideas make it fast. Variable ordering decides which region to colour next. The minimum remaining values rule, MRV, picks the region with the fewest legal colours left, so a doomed branch fails early instead of after a long detour. Inference looks ahead after each choice. Forward checking strikes the new colour from every uncoloured neighbour, and backs up the moment any neighbour runs out.

Four colours are always enough for a flat map. Appel and Haken proved it in 1976, with a computer checking the cases, and it was the first major theorem to need one. Three are not always enough, and deciding whether three will do is NP-complete, even for flat maps.

The maths

Write the map as a graph. Each region is a variable $X_i$ , each shared border is an edge in $E$ , and every variable takes one of $k$ colours.

\mathcal{X} = \{X_1, \dots, X_n\}, \qquad D_i = \{1, \dots, k\}, \qquad \mathcal{C} = \{\, X_i \ne X_j : (i, j) \in E \,\}

There are kⁿ complete colourings. Backtracking checks constraints as it goes, so it visits a small fraction of them on most maps.

Given a partial colouring $\sigma$ , a region's legal colours $L_i$ are its domain minus the colours already used by its neighbours. MRV colours the region with the smallest $L_i$ next, and breaks ties by the most uncoloured neighbours, the degree rule.

L_i = D_i \setminus \{\, \sigma(X_j) : (i, j) \in E,\ X_j \text{ coloured} \,\}, \qquad \text{next} = \arg\min_{X_i \text{ uncoloured}} \lvert L_i \rvert

Haralick and Elliott called this fail-first: if a region is going to fail, find out now.

Forward checking keeps the domains themselves up to date. After a region gets colour $c$ , every uncoloured neighbour loses $c$ , and an empty domain means this branch is dead before the search walks into it.

X_i \leftarrow c \;\Longrightarrow\; D_j \leftarrow D_j \setminus \{c\} \ \text{ for every uncoloured neighbour } X_j, \qquad \text{back up if some } D_j = \varnothing

On backtracking, every domain has to be restored, not only the region that is being undone.

Arc consistency goes one step further. Mackworth's AC-3 keeps removing any value that has no compatible value in some neighbour, until nothing changes. Forward checking is the cheap version that looks only one border away from the region just coloured.

Try it

The widget draws a made-up map of up to 16 regions on a grid and colours it by backtracking. The whole search is recorded first, so you can step through it, scrub with the step slider or play it, and the totals compare one setting with another.

Regions on the map16

Colours

Most constrained region first (MRV)Forward checking

Seed 3

Step1 of 869

Colours each region may still take

Acoloured red
Bmay still take red, ink, grey
Cmay still take red, ink, grey
Dmay still take red, ink, grey
Emay still take red, ink, grey
Fmay still take red, ink, grey
Gmay still take red, ink, grey
Hmay still take red, ink, grey
Imay still take red, ink, grey
Jmay still take red, ink, grey
Kmay still take red, ink, grey
Lmay still take red, ink, grey
Mmay still take red, ink, grey
Nmay still take red, ink, grey
Omay still take red, ink, grey
Pmay still take red, ink, grey

A struck-through swatch has been ruled out, by a coloured neighbour or by forward checking.

Step 1. A is coloured red. Placements so far: 1. Backtracks so far: 0.

Whole search: 382 placements and 366 backtracks. It found a colouring.

Maps are seeded Voronoi regions on a 24 × 14 grid. Colours are red, ink, grey and dots, so no state relies on colour alone.

Start with plain backtracking and three colours. Jump to the end: 382 placements and 366 backtracks before it finds a colouring.
Tick MRV. The same map now takes 16 placements and no backtracks at all, one per region.
Untick MRV and tick forward checking. It lands in between, at 73 placements and 57 backtracks.
Tick both. The count matches MRV alone, because MRV already counts each region's legal colours and spots a region with none left on the very next pick.
Set two colours. Plain backtracking needs 46 placements to prove no colouring exists, and MRV needs 4. Then press New map a few times on three colours. Some maps cannot be coloured with three, and plain backtracking sometimes hits the step limit first. With four colours every map works.

Where I used it

Easy to get wrong

Five traps

Undoing too little on a backtrack. Forward checking edits the neighbours' domains. Restoring only the region you are undoing leaves stale strikes behind, and the search quietly misses colourings that exist. Save the domains before each choice and put them all back.
Expecting the speed-ups to add up. MRV and forward checking overlap. On the default map, adding forward checking to MRV changes nothing at all.
Reading a stopped search as a proof. A search that hits a step or time limit has shown nothing about whether a colouring exists. Only a search that runs out of options proves there is none.
Assuming colouring is easy because four colours always work. The theorem promises a colouring exists. It does not make finding one with fewer colours cheap, and the three-colour question is NP-complete.
Forgetting value ordering. Trying first the colour that rules out the fewest options for neighbours, the least-constraining value, often finds a solution sooner. The widget always tries colours in the same order, so the effect of region ordering shows on its own.

Sources

Artificial Intelligence: A Modern ApproachRussell and Norvig, 4th edition, Pearson, 2020. Chapter 6.The standard treatment of CSPs, built around the Australia map, with backtracking, MRV, forward checking and AC-3.
Increasing tree search efficiency for constraint satisfaction problemsHaralick and Elliott, Artificial Intelligence 14(3), 1980, pp. 263–313.Where forward checking and the fail-first principle were studied side by side and measured.
Consistency in networks of relationsMackworth, Artificial Intelligence 8(1), 1977, pp. 99–118.The paper behind arc consistency and the AC-3 algorithm.
Every planar map is four colorable. Part I: DischargingAppel and Haken, Illinois Journal of Mathematics 21(3), 1977, pp. 429–490.The first half of the computer-assisted proof that four colours always suffice.