Map Colouring Puzzles: How to Use the Fewest Colours

A map colouring puzzle asks you to colour every region of a map so that no two neighbouring regions share a colour, using as few colours as you can. The quickest way to solve one is to turn the map into dots and lines, colour the most crowded regions first, and back up the moment a region has no colour left.

This guide explains the rules, how to find the fewest colours a map needs, two solving methods that work together, and why some maps refuse to be finished with fewer colours. It ends with a fully worked map, then a practice map for you to try, answer included.

What are the rules of a map colouring puzzle?

A map colouring puzzle is drawn as a set of regions, often made of squares on a grid. The rules are short.

• Every region gets exactly one colour.
• Two regions that share a stretch of border must get different colours.
• Two regions that only touch at a corner do not count as neighbours, so they may share a colour.

There are two common questions. Either find the fewest colours that will do the job, or use a fixed set of colours, with a few regions already coloured for you, and find the only colouring that fits.

The second kind is the more satisfying puzzle, because it has a single answer you can reach by pure logic, much like filling in a grid of numbers.

How do you turn a map into dots and lines?

Put one dot inside each region. Then, for every pair of regions that share a border, draw a line between their dots. The shapes and sizes of the regions vanish, and what is left is a network that keeps the only thing that matters: who touches whom.

A paper published on 22 April 2020 defines a proper colouring of a network as one that leaves no line with the same colour at both of its ends ^[1]. The same paper describes colouring of networks as a classical subject ^[1].

A proper colouring of the network is exactly a correct answer to the map puzzle. Once you have the network, you can forget the map and work only with dots and lines, which is much easier to keep in your head.

Two habits make the network useful at once. Write the number of neighbours beside each dot, and look for small groups of dots that are all joined to each other. Both tell you where the trouble will be.

Can every network come from a flat map?

No. A network that comes from a flat map can always be drawn flat on a page with no two lines crossing: put each dot inside its region and draw each line straight across the shared border. Many networks cannot be drawn like that.

The key example here is the three-and-three network. It has two rows of three dots, and every dot in one row is joined to every dot in the other.

A paper published on 25 October 2012 relies on a classic theorem: any network that contains the three-and-three network, even with extra dots added along its lines, cannot be drawn without crossings, and the paper uses this to show that one of its own networks is not flat ^[2]. The three-and-three network itself is the plainest case of that rule, so it can never be drawn flat without a crossing.

For puzzle solvers this gives a quick test. If a colouring puzzle hands you a network that contains the three-and-three network, it did not come from a flat map, so it cannot be a flat-map network.

How many colours does a map need?

The answer depends on the rings of neighbours inside the map. A ring is a chain of regions, each touching the next, that closes back on itself.

The table gives you a quick lower limit. Find the worst pattern in your map and you know you cannot do better than that number of colours. Then try to colour the map with exactly that many. If you succeed, you have reached the fewest colours. If you fail after a full search, add one more colour and try again.

What is greedy colouring?

Greedy colouring is the fast first attempt. Put your colours in a fixed list, for example red, blue, yellow, green. Go through the regions one at a time, and give each region the first colour on the list that none of its already coloured neighbours is using.

Greedy colouring never breaks the rules, but it can waste colours. The order you visit the regions matters a great deal. A good habit is to start with the region that has the most neighbours, then move on to regions with many neighbours, and leave the quiet edge regions until last. Crowded regions are the hardest to fit, so they should choose while the choice is still wide.

How does backtracking finish the job?

When greedy colouring uses too many colours, backtracking finds out whether fewer will do. Fix the number of colours you are allowed. Colour the regions one by one in order, always trying the colours in the same sequence.

1. Give the next region the first allowed colour that does not clash with its neighbours.
2. If a region has no allowed colour left, it is stuck. Go back to the previous region and move it on to its next untried colour.
3. If that region has no colours left to try either, go back one more region, and so on.
4. Stop when every region is coloured, or when you have backed up past the first region. In that case, the map cannot be done with that many colours.

When solving with a pencil, keep a small list beside each region of the colours you have already tried there. It stops you trying the same dead end twice.

How many ways can a map be coloured?

Sometimes a puzzle asks not for one colouring but for how many there are. The count of proper colourings that use only colours from a set of a given size has a name: the paper published on 22 April 2020 calls it the chromatic polynomial of the network ^[1].

That paper also defines two ways of shrinking a network: deleting a line, and contracting it, which merges the dots at its two ends into one ^[1].

They lead to a neat counting rule you can check by hand. The colourings of a network equal the colourings of the network with one line deleted, minus the colourings of the network with that same line contracted. Deleting the line lets its two ends match, and the contracted network counts exactly those matching cases, so subtracting them leaves the colourings where the ends differ.

How does the method solve a full map?

Here is an original map of seven regions, A to G, on a grid of four rows and five columns. Each letter marks which region a square belongs to.

Step one: list the neighbours. Reading along every shared side gives this table.

Step two: find the lower limit. Regions A, B and D all touch each other, which is a ring of three. So the map needs at least three colours, and two can never be enough.

Step three: try greedy colouring in alphabetical order. A takes red, B takes blue, C takes red, D takes yellow and E takes blue. Now F touches blue, red, yellow and blue again, so it needs green. G then takes blue. That is four colours, one more than the lower limit, so the order was poor.

Step four: try greedy colouring with the busiest regions first. Take F first, then B and D, then A, C and E, and G last. F takes red, B takes blue, D takes yellow, A takes red, C takes yellow, E takes blue and G takes blue. Only three colours, which matches the lower limit, so three is the fewest this map needs.

Step five: see backtracking repair the bad order. Go back to alphabetical order but allow only red, blue and yellow. A is red, B blue, C red, D yellow, E blue, and then F is stuck. E had no other colour to try, and neither had D, so back up to C and move it on to yellow. Now D is yellow, E blue, F red and G blue, and the map is finished with three colours.

Step six: solve the puzzle version. Suppose the puzzle says use red, blue and yellow only, with A red and B blue. Then every other region is forced in turn. D touches A and B, so it is yellow. E touches A and D, so it is blue. F touches B, D and E, so it is red. C touches B and F, so it is yellow. G touches C and F, so it is blue.

A computer check of every possible colouring confirms that this is the only one with three colours, A red and B blue. It also shows how the count of colourings grows with the colours you allow: none with two colours, six with three, and two hundred and eighty-eight with four.

Can you solve this practice puzzle?

This map has eight regions, A to H, on a grid of five rows and five columns. Use red, blue, yellow and green. Region C is red, D is yellow, F is green and H is blue. Colour the rest, and then explain why three colours could never be enough.

Answer: B touches C, D and F, which are red, yellow and green, so B is blue. G touches D, F and H, which are yellow, green and blue, so G is red. E touches F, G and H, which are green, red and blue, so E is yellow. A touches B, E and F, which are blue, yellow and green, so A is red.

Three colours fail because region F sits in the middle of a ring of five neighbours, A, B, D, G and E, each touching the next. An odd ring needs three colours by itself, and F touches every region in it, so F needs a fourth. A computer check of every colouring confirms that no three-colour solution exists and that the answer above is the only four-colour one with the given regions.

What mistakes should you avoid?

• Counting corner touches as borders. Regions that meet only at a point may share a colour.
• Starting with the quiet regions. Colour the region with the most neighbours first, or greedy colouring is more likely to waste colours.
• Stopping at the first answer. A colouring that works is not proof that it uses the fewest colours. Compare it with the lower limit from the rings you spotted.
• Forgetting what you tried. When backtracking, note the colours already tried at each region so you never repeat a dead end.

What colour puzzle should you try next?

Map colouring trains you to track which colours are still possible in each place and to rule the others out. Then try a short colour puzzle that asks which colour hides under a marked square.