next up previous
Next: Building Constraint Agents Up: Map Colouring Previous: Map Colouring

The Map Colouring Program

As a toy example let us write a program to colour a map so that no two neighbouring countries have the same colour. In constraint logic programs, variables start with a capital letter (eg A), and constants with a small letter (eg red).

Figure 3: A Simple Map to Colour

A generic logic program, in Prolog syntax, that tries find possible ways of colouring this map with only three colours (red, green and blue) is in figure 4.

Figure 4: A Generic Logic Program for Map Colouring

In this program the (as yet undefined) predicate ne constrains its arguments to take different values. We will show how different definitions of ne cause the program to behave in different ways.

The predicate chosen can be satisfied in three ways. At runtime the system tries each alternative in turn. If a failure occurs later in the computation, then the alternatives are tried in a last-in first-out basis.

The first definition of ne uses the original disequality of Prolog:
ne(X,Y) :- X\=Y.
If invoked when either of its arguments are uninstantiated variables, X\=Y simply fails. To avoid this incorrect behaviour it is possible to place the constraints after all the choices. In this case the program correctly detects that there is no possible colouring after checking all 81 alternatives.

A more efficient Prolog program can be written by interleaving choices and constraints, but this requires the programmer to think in terms of the operational behaviour of the program on this particular map. The same effect can be achieved much more cleanly by using the program of figure 4 with a new definition: ne(X,Y) :- X~=Y.
This disequality predicate delays until both arguments have a fixed value. It then immediately wakes up and fails if both values are the same. If the values are different it succeeds. This program detects that our map cannot be coloured with three colours after trying only 33 alternatives.

Another disequality constraint is available in CLP, which assumes its arguments have a finite set of possible values. We can use it by defining
ne(X,Y) :- X##Y.
This disequality delays until one of its arguments has a fixed value. This value is then removed from the set of possible values for the other. To obtain the advantage of X##Y it is necessary to declare the set of possible values for each variable, by writing [A,B,C,D]::[red,green,blue].

Figure 5: A Finite Domain CLP Program for Map Colouring

This program detects that the map cannot be coloured after trying only 6 alternatives.

Although this example is so trivial that it is quite simple to solve it in Prolog, the CLP program scales up to complex maps and graphs in a way that is impossible using a programming language without constraints.

next up previous
Next: Building Constraint Agents Up: Map Colouring Previous: Map Colouring

Mark Wallace
Wed Sep 3 18:36:40 BST 1997