next up previous contents
Next: Having Enough Change in Up: The Conceptual Model and Previous: The Conceptual Model and

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 :: [red,green,blue],
    ne(A,B), ne(A,C), ne(A,D), ne(B,C), ne(B,D), ne(C,D),

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 gif. 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.

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997