## 6.1 Example: Coloring a Map

### Problem Specification

Given a map showing the West European countries Netherlands, Belgium, France, Spain, Portugal, Germany, Luxemburg, Switzerland, Austria, and Italy, find a coloring such that neighboring countries have different color and a minimal number of colors is used.

### Model

We have a variable saying how many different colors we can use. Moreover, we have a variable for every country. For every pair , of countries having a border in common we impose the constraint . We represent colors as numbers. Hence we constrain all variables for countries to integers in .

### Distribution Strategy

We first distribute on , trying the numbers in ascending order. After is determined, we distribute on the variables for the countries using the usual first-fail strategy.

`fun {MapColoring Data}   Countries = {Map Data fun {\$ C#_} C end}in    proc {\$ Color}      NbColors  = {FD.decl}   in       {FD.distribute naive [NbColors]}      %% Color: Countries --> 1#NbColors      {FD.record color Countries 1#NbColors Color}      {ForAll Data       proc {\$ A#Bs}          {ForAll Bs proc {\$ B} Color.A \=: Color.B end}       end}      {FD.distribute ff Color}   end end  Data = [ austria     # [italy switzerland germany]         belgium     # [france netherlands germany luxemburg]         france      # [spain luxemburg italy]         germany     # [austria france luxemburg netherlands]         italy       # nil         luxemburg   # nil         netherlands # nil         portugal    # nil         spain       # [portugal]         switzerland # [italy france germany austria] ]`

Figure 6.1: A script for the Map Coloring Problem together with a data specification.

### Script

The script appears in Figure 6.1. It is parameterized with the specification of the map to be colored. The figure shows the specification of a map containing some European countries.

The script first creates a local variable `NbColors` that specifies the number of different colors to be used for coloring the map. Then it distributes naively on `NbColors`. Recall that a distributor blocks its thread until it has done its job. After `NbColors` is determined by distribution, the variable `Color` is constrained to a record mapping the country names to integers in `1#NbColors`. This implicitly creates the variables for the Countries. Next the script creates a propagator

`Color.A \=: Color.B`

for every pair `A`, `B` of bordering countries. Finally, the script distributes on `Color` using the first-fail strategy.

The statement

`{ExploreOne {MapColoring Data}}`

will show the search tree explored to find the first solution, which looks as follows:

`color(   austria:     1   belgium:  3   france:    1      germany:     2   italy:    2   luxemburg: 4      netherlands: 1   portugal: 1   spain:     2      switzerland: 3       )`

The search tree of `MapColoring` is interesting. First, colorings with 0, 1, 2 and 3 colors are searched and not found. Then a coloring with 4 colors is searched. Now a solution is found quickly, without going through further failure nodes. There are many solutions using 4 colors since the particular color given to a country does not matter.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)