Lesson goal: Coloring a map

Previous: Traveling between cities | Home | Next: Solving a right triangle

Suppose you have a map that looks like this (you can use any map for this, even a real one from where you live):

Your job is to color in regions of the map, so that no two regions have the same color. Sounds easy, but there's one restriction: you may not use more than 4 different colors. (You can read about this on the Wikipedia page..)

But how would one define the map to the computer? Well, regions can be defined by what other regions they are adjacent to. (In other words, by what other regions a given region touches). Prolog handles this farily simply: just give each region a name, and make up a clause called adjacent(X,Y) to describe which region Y region X come into contact with? We can have as many of these as needed, to describe all regions X touches.

In the code below, we'll define a map made up of regions A-G with the clause map(A,B,C,D,E,F,G). We'll say this clause succeeds if (:-) the regions are adjacent as shown.

Next, we'll define the colors we'd like to use (no more than 4), in this case red, blue, green, an yellow using the color clauses.

Now, here's the fun part. The list of adjacent clauses defining the map were used to physically describe the location of each region relative to those it touches. But for actually coloring the map, adjacent can only succeed if the colors of any touching regions are different. This is what adjacent(X,Y) :- color(X),color(Y),X \= Y. does.