Map Colouring

  Let us start by mapping the conceptual model for the map colouring example illustrated in figure 2.1 into a design model which uses the finite domain constraint handler of ECLiPSe.

The design model is encoded as shown below.

:- lib(fd).

coloured(Countries) :-
    Countries=[A,B,C,D],
    Countries :: [red,green,blue],
    ne(A,B), ne(A,C), ne(A,D), ne(B,C), ne(B,D), ne(C,D),
    labeling(Countries).

ne(X,Y) :- X##Y.

A Finite Domain CLP Program for Map Colouring  

The design model extends the conceptual model in four ways.

1. The ECLiPSe finite domain library is loaded (using :- lib(fd)).
2. An explicit finite domain is associated with each decision variable (using Countries :: [red, green, blue]).
3. The finite domain built-in disequality constraint is used to implement the ne constraint (using ne(X,Y) :- X##Y). ## is a special syntax for disequality used by the finite domain constraint solver.
4. This program includes a search algorithm, invoked by the goal labeling(Countries). As we shall see later, this predicate tries choosing, for each of the variables A, B, C and D in turn, a value from its domain. It succeeds when a combination of values has been found that satisfies the constraints.

Naturally this is a toy example, and it is not always so easy to turn a conceptual model, such as the ECLiPSe program in figure 2.1, into a design model, such as the program in figure . Nevertheless constraint logic programming, and in particular ECLiPSe, have made a lot of progress in achieving a close relationship between the conceptual model and the design model. The different components of the ECLiPSe system all support the separate development of a clear, correct conceptual model, and an efficient design model, and they also support the mapping between the two.