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 # mathend000# nbColors.

Branching Strategy

We first branch on nbColors, trying the numbers 1, 2,... mathend000# 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{| mathend000#1 | mathend000#}, belgium = intvar{| mathend000#2 | mathend000#}, france = intvar{| mathend000#1 | mathend000#},
germany = intvar{| mathend000#3 | mathend000#}, italy = intvar{| mathend000#3 | mathend000#}, luxemburg = intvar{| mathend000#4 | mathend000#},
nbColors = intvar{| mathend000#4 | mathend000#}, netherlands = intvar{| mathend000#1 | mathend000#}, portugal = intvar{| mathend000#1 | mathend000#},
spain = intvar{| mathend000#2 | mathend000#}, switzerland = intvar{| mathend000#2 | mathend000#}}