next up previous contents
Next: The fd Integer Arithmetic Up: The fd (Finite Domain) Previous: The fd (Finite Domain)

The fd Symbolic Finite Domain Facilities

In figures 2.1 and 2.3.1, above, we showed a map colouring problem and its solution. The domains associated with the countries were red, green and blue. These were declared as finite domains, with the usual syntax: X :: [red, green, blue].

The problem could have been modelled using numbers to represent colours, so there is no extra power in allowing symbolic finite domains as well as numeric ones. However when developing ECLiPSe programs for real problems, it is a very great help to use meaningful names so as to distinguish different types of finite domain variables. In particular it is crucial during debugging!

figure gif illustrates the basic constraints on finite domain variables, and predicates for accessing and searching these domains.

[eclipse 1]: lib(fd).
*       fd loaded

[eclipse 2]:  X::[a,b,c].
*       X = X{[a, b, c]}
*       yes.

[eclipse 3]: X::[a, 3.1, 7].
*       X = X{[3.0999999, 7, a]}
*       yes.

[eclipse 4]: X::[a,b,c], dom(X,List).
*       X = X{[a, b, c]}
*       List = [a, b, c]
*       yes.

[eclipse 5]: X::[a,b,c], Y::[b,c,d], X#=Y.
*       X = X{[b, c]}
*       Y = X{[b, c]}
*       yes.

[eclipse 6]: X::[a,b,c], X##b.
*       X = X{[a, c]}
*       yes.

[eclipse 7]: X::[a,b,c], indomain(X).
*       X = a     More? (;) 
*       X = b     More? (;) 
*       X = c
*       yes.

[eclipse 8]: [X,Y,Z]::[a,b,c], X##Y, Y##Z, X##Z, labeling([X,Y,Z]).
*       X = a
*       Y = b
*       Z = c     More? (;) 

*       X = a
*       Y = c
*       Z = b     More? (;) 
*       yes.

[eclipse 9]:  [X,Z]::[a,b,c], Y::[a,c], 
              deleteff(Var,[X,Y,Z],Rest), indomain(Var).

*       X = X{[a, b, c]}
*       Y = a
*       Z = Z{[a, b, c]}
*       Rest = [X{[a, b, c]}, Z{[a, b, c]}]
*       Var = a     More? (;) 
*       yes.
Using Symbolic Finite Domains  

The second query associates a symbolic finite domain with the variable X. In response ECLiPSe prints out the variable name and its newly assigned domain. The fact that the variable has an associated domain does not require any changes in other parts of the program, where X may be treated as an ordinary variable.

Query 3 shows that symbolic domains can include values of different types.

Query 4 shows the use of the dom predicate to retrieve the domain associated with a variable.

Queries 5 and 6 illustrate the equality and disequality constraints, and their effects on the domains of the variables involved. Finite domain constraints use a special syntax to make explicit which constraint library is to handle the constraint, for example it uses #= instead of =.

Queries 7, 8 and 9 illustrate search. Strictly one would not expect search predicates to belong to a constraint library, but in fact search and constraint propagation are closely connected.

Query 7 shows the indomain predicate instantiating a domain variable X to a value in its domain. ECLiPSe asks if more answers are required, and when the user does indeed ask for more, another value from the domain of X is chosen, and X is instantiated to that value instead. When the user asks for more again, X is instantiated to the third and last value in its domain, and this time ECLiPSe doesn't offer the user any further choices, but simply outputs yes.

Query 8 illustrates the built-in finite domain labeling predicate. This predicate simply invokes indomain on each variable in turn in its argument. In this case it calls indomain first on X, then Y and then Z. However the variables are constrained to take different values by three disequality constraints, and only those labelings that satisfy the constraints are admitted. Consequently this query has six different answers, though the user stops asking for more after the second answer.

Query 9 illustrates a heuristic based on the fail first principle. In choosing the next decision to make, when solving a problem, it is often best to make the choice with the fewest alternatives first. The predicate deleteff selects a variable from a set of variables which has the fewest alternatives: i.e. the smallest finite domain. In the example there are three variables, X, Y and Z representing three decisions, deleteff picks out Y because it has the smallest domain, and then indomain selects a value for Y. The third argument of deleteff is an output argument: Rest returns the remaining variables after the selected one has been removed. These are the decisions yet to be made.

next up previous contents
Next: The fd Integer Arithmetic Up: The fd (Finite Domain) Previous: The fd (Finite Domain)

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