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.

Viewpoint

This viewpoint's variable set consists of eleven elements: we have a variable nbColors saying how many different colors we can use. Moreover, we have a vector countries1 , containing a variable for every country . We represent colors as numbers. Hence we constrain all variables for countries to integers in 1 # nbColors.

Branching Strategy

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

Script

The script in Listing 12 uses the procedure borderTo to guarantee that no two countries that have a common border can have the same color.

fun mapColoring space =
 let
    val nbColors = FD.range(space,(1,10))
    val countries as #[au,ge,ne,sw,be,ita,po,fr,lu,sp] =
            FD.rangeVec(space,10,(1,10))
    (* borderTo gets a country and its neighbours and
          ensures they do not have the same color *) 
    fun borderTo(space,c,nvec)=
                Vector.app(fn x => FD.rel(space,c,FD.NQ,x))nvec
 in
    FD.branch(space,#[nbColors],FD.B_NONE,FD.B_MIN);
    Vector.app(fn x => FD.rel(space,x,FD.LQ,nbColors))countries;
    borderTo(space,au,#[ita,sw,ge]);
    borderTo(space,be,#[fr,ne,ge,lu]);
    borderTo(space,fr,#[sp,lu,ita]);
    borderTo(space,ge,#[au,fr,lu,ne]);
    borderTo(space,sp,#[po]);
    borderTo(space,sw,#[ita,fr,ge,au]);
    FD.branch(space,countries,FD.B_SIZE_MIN,FD.B_MIN);
    { netherlands = ne, belgium = be, france = fr, spain = sp,
      portugal = po, germany = ge, luxemburg = lu, italy = ita,
      switzerland = sw, austria = au, nbColors}
 end

The search tree of mapColoring is interesting.First, colorings with 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.

The statement

Explorer.exploreOne(mapColoring);

results in the following solution:

{austria = intvar{|1 |}, belgium = intvar{|2 |}, france = intvar{|1 |},
germany = intvar{|3 |}, italy = intvar{|3 |}, luxemburg = intvar{|4 |},
nbColors = intvar{|4 |}, netherlands = intvar{|1 |}, portugal = intvar{|1 |},
spain = intvar{|2 |}, switzerland = intvar{|2 |}}