Can Four Colors Paint Any Map of Nepal?

All 77 districts

Now the whole map. The Kathmandu Valley’s tiny districts are drawn again, larger, in the box at the top right.

Three colors for the Valley?

Could some map force five? Try drawing five countries that all touch each other: one is always shut out. But a map might force five in a cleverer way. People asked for 124 years whether four colors are always enough, for every map anyone could ever draw. The answer needed a computer.

One district at a time

A computer can color as you did: take the districts in some order, and give each the smallest color number none of its colored neighbors has. That is greedy coloring: it takes what looks best right now, and never goes back.

Try it on the provinces: each tap gives a province the smallest color number it can have.

Now let the computer color all 77 districts, a district at a time, in different orders.

A map is a graph

For coloring, only which districts touch which matters. So draw a dot for each district and a line for each pair that shares a border: a graph, as in Grade 10 (dots are vertices, lines edges). Coloring the map is coloring the dots so no line joins two of the same color.

Places that meet only at a point aren’t neighbors (four farms meeting at one corner post can share two colors). So Nepal’s districts make a graph of 77 dots and 188 lines. The shortest shared border, Ramechhap–Sindhupalchok, is under a kilometer, but it counts.

Why greedy gets stuck

When greedy reaches a district whose neighbors show 1, 2, 3 and 4, it must use 5, even if a different choice much earlier would have left a color free.

Busiest first

A better rule picks, at every step, the district hardest to color right now: the one whose neighbors show the most different colors (if several tie, the first on the list). It is the one most likely to get stuck, so it goes while it still has a choice. Daniel Brélaz published this rule in 1979 as DSatur; here it is busiest first. (His version breaks a tie by taking the district with the most uncolored neighbors; on these maps it gives the same counts.)

Press Busiest first in the last widget: four colors. It starts at Jhapa (the first on the list) and spreads west, always to a district hemmed in by colors, each reached while it still has one free.

The map as data (Python, from Grade 8)

The programs use the page’s own module, nepal.py, made from the widgets’ map. DISTRICTS lists the 77 names, east to west. NEIGHBORS is a dictionary: a list whose items are looked up by name, not number. NEIGHBORS['Kathmandu'] lists Kathmandu’s neighbors. (Dictionaries come properly in Grade 9.)

from nepal import DISTRICTS, NEIGHBORS print(len(DISTRICTS), 'districts')print('Kathmandu borders', NEIGHBORS['Kathmandu']) lines = 0most = DISTRICTS[0]for d in DISTRICTS:    lines = lines + len(NEIGHBORS[d])    if len(NEIGHBORS[d]) > len(NEIGHBORS[most]):        most = dprint(lines // 2, 'shared borders')print(most, 'has the most neighbors:', len(NEIGHBORS[most])) valley = ['Kathmandu', 'Lalitpur', 'Bhaktapur', 'Kavrepalanchok']for a in valley:    for b in valley:        if a != b and b not in NEIGHBORS[a]:            print(a, 'does not touch', b)print('Checked the Valley four.')

77 districtsKathmandu borders ['Bhaktapur', 'Dhading', 'Kavrepalanchok', 'Lalitpur', 'Makwanpur', 'Nuwakot', 'Sindhupalchok']188 shared bordersUdayapur has the most neighbors: 9Checked the Valley four.

Each border is counted from both sides, so the program halves the count. Sindhuli and Makwanpur have 9 neighbors too: > keeps the first it finds. The Valley check printed nothing: each of the four touches the other three.

Check a coloring

A coloring is a dictionary too: colors['Jhapa'] is Jhapa’s color, 1, 2, 3… This function lists every border with the same color on both sides; d < n (alphabetical order) lists each pair once.

from nepal import DISTRICTS, NEIGHBORS def clashes(colors):    found = []    for d in DISTRICTS:        for n in NEIGHBORS[d]:            if d < n and colors[d] == colors[n]:                found.append(d + ' and ' + n)    return found # colors in turn down the list: 1, 2, 3, 4, 1, 2, 3, 4…colors = {}for i in range(len(DISTRICTS)):    colors[DISTRICTS[i]] = i % 4 + 1print(len(clashes(colors)), 'clashes, for example', clashes(colors)[:2])

40 clashes, for example ['Ilam and Morang', 'Dhankuta and Panchthar']

colors = {} makes an empty dictionary; colors[name] = … adds a name. Taking turns gives 40 clashes: four colors are enough only if chosen with care.

Greedy coloring

For each district in order, greedy collects its colored neighbors’ colors (n in colors asks whether n has one yet), then counts up from 1 to the first color not among them.

from nepal import DISTRICTS, NEIGHBORS def greedy(order):    colors = {}    for d in order:        used = []        for n in NEIGHBORS[d]:            if n in colors:                used.append(colors[n])        c = 1        while c in used:            c = c + 1        colors[d] = c    return colors def color_districts():    return greedy(DISTRICTS) colors = color_districts()print('East to west:', max(colors.values()), 'colors')print('Color 5 went to', [d for d in DISTRICTS if colors[d] == 5])print('A to Z:', max(greedy(sorted(DISTRICTS)).values()), 'colors')

East to west: 5 colorsColor 5 went to ['Makwanpur', 'Doti']A to Z: 6 colors

max(colors.values()) is the number of colors used; sorted(DISTRICTS) is the list in alphabetical order. The widget below paints what your color_districts() gives back.

A thousand orders

Is there an order greedy does well with? random.shuffle(order) mixes a list, and random.seed(1) makes the “random” orders the same every run, so you get this page’s counts.

import randomfrom nepal import DISTRICTS, NEIGHBORS def greedy(order):    colors = {}    for d in order:        used = []        for n in NEIGHBORS[d]:            if n in colors:                used.append(colors[n])        c = 1        while c in used:            c = c + 1        colors[d] = c    return colors random.seed(1)count = [0, 0, 0, 0, 0, 0, 0, 0]       # count[k]: orders that needed k colorsfor i in range(1000):    order = DISTRICTS.copy()    random.shuffle(order)    k = max(greedy(order).values())    count[k] = count[k] + 1for k in range(4, 8):    print(k, 'colors:', count[k], 'orders')

4 colors: 0 orders5 colors: 618 orders6 colors: 379 orders7 colors: 3 orders

Busiest first

Each time round, busiest first counts the different colors around every uncolored district (seen, each color once) and takes the one with the most.

from nepal import DISTRICTS, NEIGHBORS def busiest_first(names, neighbors):    colors = {}    while len(colors) < len(names):        best = ''        best_seen = -1        for d in names:            if d not in colors:                seen = []                for n in neighbors[d]:                    if n in colors and colors[n] not in seen:                        seen.append(colors[n])                if len(seen) > best_seen:                    best = d                    best_seen = len(seen)        used = []        for n in neighbors[best]:            if n in colors:                used.append(colors[n])        c = 1        while c in used:            c = c + 1        colors[best] = c    return colors def color_districts():    return busiest_first(DISTRICTS, NEIGHBORS) colors = color_districts()print('Busiest first:', max(colors.values()), 'colors')print('The first five it colored:', list(colors)[:5])

Busiest first: 4 colorsThe first five it colored: ['Jhapa', 'Ilam', 'Morang', 'Panchthar', 'Dhankuta']

A dictionary keeps the order names were added, so list(colors) is the order busiest first chose. It takes the map as parameters, so it can color any map: you will need that below.

• Four colors are enough for Nepal, and the Valley shows three are not.
• Greedy almost never finds them. In a thousand random orders it needed 5 or more every time: 618 times five, 379 six, 3 seven.
• The order is everything. Every map has an order in which greedy does as well as the best coloring: list every district of color 1, then every district of color 2, and so on. When a color-1 district’s turn comes, only other color-1 districts are colored, none of them its neighbor, so 1 is free; and so on up.

greedy and busiest_first are kept as a module, coloring.py, for the programs below.

from nepal import DISTRICTS, NEIGHBORSfrom coloring import greedy, busiest_first four = busiest_first(DISTRICTS, NEIGHBORS)order = []for c in [1, 2, 3, 4]:    for d in DISTRICTS:        if four[d] == c:            order.append(d)print('Order:', order[:4], '...')again = greedy(order, NEIGHBORS)print('Greedy in this order:', max(again.values()), 'colors')print('Same colors as busiest first?', again == four)

Order: ['Jhapa', 'Panchthar', 'Sankhuwasabha', 'Sunsari'] ...Greedy in this order: 4 colorsSame colors as busiest first? True

So the right order exists for every map, but to write it down you must already have the coloring. Checking a coloring is quick, as your clashes shows; finding one with the fewest colors is hard. Deciding whether three colors are enough for a map is one of computer science’s famous hard problems: nobody knows a method fast for every map. For four colors on a flat map, the answer is always yes.

Busiest first can fail too. Here is a made-up map of nine regions that can be colored with four. Run busiest first on it.

from coloring import busiest_first NINE = {    'A': ['B', 'C', 'F', 'I'], 'B': ['A', 'C', 'G', 'H'], 'C': ['A', 'B', 'E', 'G', 'I'],    'D': ['E', 'F', 'G', 'H'], 'E': ['C', 'D', 'F', 'G', 'I'], 'F': ['A', 'D', 'E', 'H', 'I'],    'G': ['B', 'C', 'D', 'E', 'H'], 'H': ['B', 'D', 'F', 'G'], 'I': ['A', 'C', 'E', 'F'],}colors = busiest_first(list(NINE), NINE)print(colors)print(max(colors.values()), 'colors')

{'A': 1, 'B': 2, 'C': 3, 'G': 1, 'E': 2, 'I': 4, 'F': 3, 'D': 4, 'H': 5}5 colors

By the time it reaches H, H’s neighbors have all four colors. Can you color the nine with four by hand?

Coloring is everywhere. In an exam timetable, each subject is a dot, a line joins two subjects some student takes both of, and the colors are the days. Radio stations near each other need different frequencies, colored the same way, and so are the few fast registers a processor keeps numbers in.

★ Count the clashes (Python, from Grade 8)

Write count_clashes(colors, neighbors): how many borders have the same color on both sides. neighbors is a dictionary like NEIGHBORS, and colors gives each region a color. Count each border once.

def count_clashes(colors, neighbors):    # colors: {'A': 1, 'B': 2, …}; neighbors: {'A': ['B', …], …}    return 0 print(count_clashes({'A': 1, 'B': 1, 'C': 2}, {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}))

★★ Greedy, in any order (Python, from Grade 8)

Write greedy_colors(order, neighbors): color the regions greedily in the order given, and give back a list of their colors in that same order. greedy_colors(['A', 'B', 'C'], …) for three regions that all touch gives [1, 2, 3].

def greedy_colors(order, neighbors):    return [] print(greedy_colors(['A', 'B', 'C'], {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}))

★★★ Can it be colored? (Python, from Grade 8)

Write can_color(neighbors, k): True if the regions can be colored with at most k colors and no clashes, False if they can’t. The tests have up to nine regions, including the nine-region map above with k = 4, where busiest first fails.

def can_color(neighbors, k):    return True print(can_color({'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}, 2))

• Grade 8, Functions: functions like greedy and clashes that answer a question.
• Grade 9, Lists, Strings and Dictionaries: dictionaries properly, the way NEIGHBORS is kept.
• Grade 10, Graphs, Maps, Routes and Networks: graphs, and searching them for routes.
• Can you cross the river with the tiger, the goat and the grass? Another puzzle that becomes a graph of dots and lines.
• How many ways round Bhaktapur’s temples? Trying every route, and how fast that stops working.