Map colouring
No two neighbours may share a colour. Greedy orders grab colours as they go, DSatur picks the hardest region first, and backtracking proves when three will never do. Then try it yourself.
The numbers
How it works
Colouring a graph
Shrink every region to a dot and join two dots when their regions share a stretch of border: the map becomes a graph (turn on graph to see it). Colouring the map so neighbours differ is colouring the graph so that every line has two different ends, and the fewest colours that can do it is the graph's chromatic number, χ. Touching at a single point does not count: in Rectangulia, four states can meet at a corner like the real Four Corners and still all share one colour.
Four is always enough
In 1852 Francis Guthrie, colouring the counties of England, guessed that four colours suffice for any map. Alfred Kempe published a proof in 1879; eleven years later Percy Heawood found the hole in it, though Kempe's idea still proves that five are enough. The four colour theorem was finally proved by Kenneth Appel and Wolfgang Haken in 1976, by reducing every map to 1,936 unavoidable configurations and checking each one by computer, the first big theorem to need one. Robertson, Sanders, Seymour and Thomas cut that to 633 in 1996, and in 2005 Georges Gonthier checked the whole proof, line by line, in the Coq proof assistant. The theorem holds for planar maps, where every country is one connected piece. Real countries cheat: French Guiana makes France a neighbour of Brazil, Kaliningrad puts Russia next to Poland, and with enough exclaves a map can need more than four. The world still gets by with four, and with sea links on, the Channel Tunnel and other crossings join islands to the mainland too. Islands with no links are free to take any colour.
Greedy and DSatur
Greedy colouring visits the regions in some order and gives each the lowest colour its coloured neighbours have not taken. It never backtracks, so it is fast, but the order matters: early choices box in later regions and it can need five or six where four would do (try "as listed" on Voronoi isles). Largest first colours the busiest regions while they still have options. Smallest last peels off the region with the fewest neighbours, again and again, then colours in reverse; every planar map has a region with at most five neighbours, so this never needs more than six. DSatur (Brélaz, 1979) always picks the uncoloured region whose neighbours already use the most different colours, the one closest to trouble.
Backtracking
To find χ for certain, backtracking tries a colour, moves on, and undoes the choice when it hits a dead end. Forward checking crosses the chosen colour off every neighbour's list straight away, so a region left with no colours (flashed red) is caught before going deeper; MRV (minimum remaining values) then always decides the region with the fewest colours left, the same instinct as DSatur. Two more tricks keep the proof small: regions with fewer than k neighbours are set aside, because they can always be coloured last, and a new colour is only ever the next unused one, so the k! ways of renaming the same colouring are tried once. When every branch for three colours fails, the search has proved that three is impossible. Deciding whether any map can be 3-coloured is NP-complete, so no known method beats exponential time in the worst case, while 4 colours for a planar map is guaranteed and 2 is easy. The same search fills sudoku grids (a sudoku is a graph colouring with nine colours, where every cell borders its row, column and box), timetables and register allocators, and wave function collapse is a cousin: it too picks the most constrained cell next and propagates what that rules out.
Kempe chains and local search
When a region finds all four colours around it, take two of them, say red and blue, and follow the red-blue Kempe chain from a red neighbour: every region reachable through red and blue only. Swap red and blue along the whole chain and the map is still fine, but if the chain never reaches a blue neighbour, that red neighbour is now blue and red is free. Kempe's 1879 argument leant on this and was almost right; on these maps the swaps usually work and sometimes get stuck. Local search starts from random colours and keeps recolouring a clashing region to whatever clashes least, with a little randomness to escape plateaus. It never proves anything but is often quick.
The countries come from the atlas (Natural Earth), with borders taken from the shared edges of its map; the made-up maps are Voronoi cells, like those in Voronoi city, or straight-ruled states.
A question a student could ask over a map of English counties needed a century, a computer and a proof assistant to settle, and four crayons still do the job.