COLORING A MAP

Assigning colors to the countries on a map so no two adjacent countries have the same color is easy in Prolog. We define a tail-recursive map coloring routine that takes a list of country-color pairs representing color assignments that have already been made as input and returns a list of color-country pairs that includes all the countries on the map. This routine checks first to see if any countries remain to be colored. If so, it assigns it a color that is not prohibited by previous color assignments, adds this new country-color pair to the list, and calls itself recursively. Otherwise, the current list of color assignments is complete.

color_map(List,Solution) :- remaining(Country,List),
                            color(Hue),
                            \+ prohibited(Country,Hue,List),
                            write(Country),
                            nl,
                            color_map([[Country,Hue]|List],Solution).
color_map(Solution,Solution).

We have added the write command so we can watch what the routine is doing as it searches for a solution.

We have added the write command so we can watch what the routine is doing as it searches for a solution:

prohibited(Country,Hue,List) :- borders(Country,Neighbor),
                                member([Neighbor,Hue],List).

It can be proven mathematically that we will never need more than four colors for any map. So we store four colors in clauses for the predicate color/1. We have selected the colors red, blue, green and yellow.

The predicate prohibited/3 calls the predicate borders/2. We list each pair of neighboring countries using the predicate beside/2. Then we use beside to define borders.

borders(Country,Neighbor) :- beside(Country,Neighbor).
borders(Country,Neighbor) :- beside(Neighbor,Country).

We call the main predicate map. Used as a query, this predicate calls color_map with an initially empty list of country-color pairs. When color_map returns a complete coloring scheme for the map, it is displayed using the writeln/1 routine

Finally, we need a representation of the map itself. This is a series of clauses for the predicates country and beside. In the following listing, we have included geographical data for South America.

% Only four colors are ever needed
color(red).
color(blue).
color(green).
color(yellow).
member(X,[X|_]).
member(X,[_|Y]) :-
member(X,Y).

% Geographical data for South America
country(antilles). country(argentina).
country(bolivia). country(brazil).
country(columbia). country(chile).
country(ecuador). country(french_guiana).
country(guyana). country(paraguay).
country(peru). country(surinam).
country(uruguay). country(venezuela).
beside(antilles,venezuela). beside(argentina,bolivia).
beside(argentina,brazil). beside(argentina,chile).
beside(argentina,paraguay). beside(argentina,uruguay).
beside(bolivia,brazil). beside(bolivia,chile).
beside(bolivia,paraguay). beside(bolivia,peru).
beside(brazil,columbia). beside(brazil,french_guiana).
beside(brazil,guyana). beside(brazil,paraguay).
beside(brazil,peru). beside(brazil,surinam).
beside(brazil,uruguay). beside(brazil,venezuela).
beside(chile,peru). beside(columbia,ecuador).
beside(columbia,peru). beside(columbia,venezuela).
beside(ecuador,peru). beside(french_guiana,surinam).
beside(guyana,surinam). beside(guyana,venezuela).