Previous Up Next

Chapter 2  The Finite Domains Library

The library fd.pl implements constraints over finite domains that can contain integer as well as atomic (i.e. atoms, strings, floats, etc.) and ground compound (e.g. f(a, b)) elements. Modules that use the library must start with the directive
:- use_module(library(fd)).

2.1  Terminology

Some of the terms frequently used in this chapter are explained below.
domain variable
A domain variable is a variable which can be instantiated only to a value from a given finite set. Unification with a term outside of this domain fails. The domain can be associated with the variable using the predicate ::/2. Built-in predicates that expect domain variables treat atomic and other ground terms as variables with singleton domains.

integer domain variable
An integer domain variable is a domain variable whose domain contains only integer numbers. Only such variables are accepted in inequality constraints and in rational terms. Note that a non-integer domain variable can become an integer domain variable when the non-integer values are removed from its domain.

integer interval
An integer interval is written as
Min .. Max
with integer expressions MinMax and it represents the set
{Min, Min + 1, ..., Max}.


linear term
A linear term is a linear integer combination of integer domain variables. The constraint predicates accept linear terms even in a non-canonical form, containing functors +, - and *, e.g.
5*(3+(4−6)*YX*3).
If the constraint predicates encounter a variable without a domain, they give it a default domain -10000000..10000000. Note that arithmetic operations on linear terms are performed with standard machine word integers without any overflow checks. If the domain ranges or coefficients are too large, the operation will not yield correct results. Both the maximum and minimum value of a linear term must be representable in a machine word, and so must the maximum and minimum value of every ci xi term.

rational term
A rational term is a term constructed from integers and integer domain variables using the arithmetic operations +, −, *, /. Besides that, every subexpression of the form VarA/VarB must have an integer value in the solution. The system replaces such a subexpression by a new variable X and adds a new constraint VarA #= VarB * X. Similarly, all subexpressions of the form VarA*VarB are replaced by a new variable X and a new constraint X #= VarA * VarB is added, so that in the internal representation, the term is converted to a linear term.

constraint expression
A constraint expression is either an arithmetic constraint or a combination of constraint expressions using the logical FD connectives #/\/2, #\//2, #=>/2, #<=>/2, #\+/1.

2.2  Constraint Predicates

?Vars :: ?Domain
Vars is a variable or a list of variables with the associated domain Domain. Domain can be a closed integer interval denoted as Min .. Max, or a list of intervals and/or atomic or ground elements. Although the domain can contain any compound terms that contain no variable, the functor ../2 is reserved to denote integer intervals and thus 1..10 always means an interval and a..b is not accepted as a compound domain element.

If Vars is already a domain variable, its domain will be updated according to the new domain; if it is instantiated, the predicate checks if the value lies in the domain. Otherwise, if Vars is a free variable, it is converted to a domain variable. If Vars is a domain variable and Domain is free, it is bound to the list of elements and integer intervals representing the domain of the variable (see also dvar_domain/2 which returns the actual domain).

When a free variable obtains a finite domain or when the domain of a domain variable is updated, the constrained list of its suspend attribute is woken, if it has one.

integers(+Vars)
This constrains the list of variables Vars to have integer domains. Any non-domain variables in Vars will be given the default integer domain.

::(?Var, ?Domain, ?B)
B is equal to 1 iff the domain of the finite domain variable Var is a subset of Domain and 0 otherwise.

atmost(+Number, ?List, +Val)
At most Number elements of the list List of domain variables and ground terms are equal to the ground value Val.

constraints_number(+DVar, -Number)
Number is the number of constraints and suspended goals currently attached to the variable DVar. Note that this number may not correspond to the exact number of different constraints attached to DVar, as goals in different suspending lists are counted separately. This predicate is often used when looking for the most or least constrained variable from a set of domain variables (see also deleteffc/3).

element(?Index, +List, ?Value)
The Index'th element of the ground list List is equal to Value. Index and Value can be either plain variables, in which case a domain will be associated to them, or domain variables. Whenever the domain of Index or Value is updated, the predicate is woken and the domains are updated accordingly.

fd_eval(+E)
The constraint expression E is evaluated on runtime and no compile-time processing is performed. This might be necessary in the situations where the default compile-time transformation of the given expression is not suitable, e.g. because it would require type or mode information.

indomain(+DVar)
This predicate instantiates the domain variable DVar to an element of its domain; on backtracking the subsequent values are taken. It is used, for example, to find a value of DVar which is consistent with all currently imposed constraints. If DVar is a ground term, it succeeds. Otherwise, if it is not a domain variable, an error is raised.

is_domain(?Term)
Succeeds if Term is a domain variable.

is_integer_domain(?Term)
Succeeds if Term is an integer domain variable.

min_max(+Goal, ?C)
If C is a linear term, a solution of the goal Goal is found that minimises the value of C. If C is a list of linear terms, the returned solution minimises the maximum value of terms in the list. The solution is found using the branch and bound method; as soon as a partial solution is found that is worse than a previously found solution, failure is forced and a new solution is searched for. When a new better solution is found, the bound is updated and the search restarts from the beginning. Each time a new better solution is found, the event 280 is raised. If a solution does not make C ground, an error is raised, unless exactly one variable in the list C remains free, in which case the system tries to instantiate it to its minimum.

minimize(+Goal, ?Term)
Similar to min_max/2, but Term must be an integer domain variable. When a new better solution is found, the search does not restart from the beginning, but a failure is forced and the search continues. Each time a new better solution is found, the event 280 is raised. Often minimize/2 is faster than min_max/2, sometimes min_max/2 might run faster, but it is difficult to predict which one is more appropriate for a given problem.

min_max(+Goal, ?Template, ?Solution, ?C)
minimize(+Goal, ?Template, ?Solution, ?Term)
Similar to min_max/2 and minimize/2, but the variables in Goal do not get instantiated to their optimum solutions. Instead, Solutions will be unified with a copy of Template where the variables are replaced with their minimized values. Typically, the template will contain all or a subset of Goal's variables.

min_max(+Goal, ?C, +Low, +High, +Percent)
minimize(+Goal, ?Term, +Low, +High, +Percent)
Similar to min_max/2 and minimize/2, however the branch and bound method starts with the assumption that the value to be minimised is less than or equal to High. Moreover, as soon as a solution is found whose minimised value is less than Low, this solution is returned. Solutions within the range of Percent % are considered equivalent and so the search for next better solution starts with a minimised value Percent % less than the previously found one. Low, High and Percent must be integers.

min_max(+Goal, ?C, +Low, +High, +Percent, +Timeout)
minimize(+Goal, ?Term, +Low, +High, +Percent, +Timeout)
Similar to min_max/5 and minimize/5, but after Timeout seconds the search is aborted and the best solution found so far is returned.

min_max(+Goal, ?Template, ?Solution, ?C, +Low, +High, +Percent, +Timeout)
minimize(+Goal, ?Template, ?Solution, ?Term, +Low, +High, +Percent, +Timeout)
The most general variants of the above, with all the optinal parameters.

2.3  Arithmetic Constraint Predicates

?T1 #\= ?T2
The value of the rational term T1 is not equal to the value of the rational term T2.

?T1 #< ?T2
The value of the rational term T1 is less than the value of the rational term T2.

?T1 #<= ?T2
The value of the rational term T1 is less than or equal to the value of the rational term T2.

?T1 #= ?T2
The value of the rational term T1 is equal to the value of the rational term T2.

?T1 #> ?T2
The value of the rational term T1 is greater than the value of the rational term T2.

?T1 #>= ?T2
The value of the rational term T1 is greater than or equal to the value of the rational term T2.

2.4  Logical Constraint Predicates

The logical constraints can be used to combine simpler constraints and to build complex logical constraint expressions. These constraints are preprocessed by the system and transformed into a sequence of evaluation constraints and arithmetic constraints. The logical operators are declared with the following precedences:
:- op(750, fy, #\+).
:- op(760, yfx, #/\).
:- op(770, yfx, #\/).
:- op(780, yfx, #=>).
:- op(790, yfx, #<=>).
#\+ +E1
E1 is false, i.e. the logical negation of the constraint expression E1 is imposed.

+E1 #/\+E2
Both constraint expressions E1 and E2 are true. This is equivalent to normal conjunction (E1, E2).

+E1 #\/+E2
At least one of constraint expressions E1 and E2 is true. As soon as one of E1 or E2 becomes false, the other constraint is imposed.

+E1 #=> +E2
The constraint expression E1 implies the constraint expression E2. If E1 becomes true, then E2 is imposed. If E2 becomes false, then the negation of E1 will be imposed.

+E1 #<=> +E2
The constraint expression E1 is equivalent to the constraint expression E2. If one expression becomes true, the other one will be imposed. If one expression becomes false, the negation of the other one will be imposed.

2.5  Evaluation Constraint Predicates

These constraint predicates evaluate the given constraint expression and associate its truth value with a boolean variable. They can be very useful for defining more complex constraints. They can be used both to test entailment of a constraint and to impose a constraint or its negation on the current constraint store.
?B isd +Expr
B is equal to 1 iff the constraint expression Expr is true, 0 otherwise. This predicate is the constraint counterpart of is/2 — it takes a constraint expression, transforms all its subexpressions into calls to predicates with arity one higher and combines the resulting boolean values to yield B. For instance,
B isd X #= Y
is equivalent to
#=(X, Y, B)


#<(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is less than the value of the rational term T2, 0 otherwise.

#<=(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is less than or equal to the value of the rational term T2, 0 otherwise.

#=(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is equal to the value of the rational term T2, 0 otherwise.

#\=(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is different from the value of the rational term T2, 0 otherwise.

#>(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is greater than the value of the rational term T2, 0 otherwise.

#>=(?T1, ?T2, ?B)
B is equal to 1 iff the value of the rational term T1 is greater than or equal to the value of the rational term T2, 0 otherwise.

#/\(+E1, +E2, ?B)
B is equal to 1 iff both constraint expressions E1 and E2 are true, 0 otherwise.

#\/(+E1, +E2, ?B)
B is equal to 1 iff at least one of the constraint expressions E1 and E2 is true, 0 otherwise.

#<=>(+E1, +E2, ?B)
B is equal to 1 iff the constraint expression E1 is equivalent to the constraint expression E2, 0 otherwise.

#=>(+E1, +E2, ?B)
B is equal to 1 iff the constraint expression E1 implies the constraint expression E2, 0 otherwise.

#\+(+E1, ?B)
B is equal to 1 iff E1 is false, 0 otherwise.

2.6  CHIP Compatibility Constraints Predicates

These constraints, defined in the module fd_chip, are provided for CHIP v.3 compatibility and they are defined using native ECLiPSe constraints. Their source is available in the file fd_chip.pl.
?T1 ## ?T2
The value of the rational term T1 is not equal to the value of the rational term T2.

alldistinct(?List)
All elements of List (domain variables and ground terms) are pairwise different.

deleteff(?Var, +List, -Rest)
This predicate is used to select a variable from a list of domain variables which has the smallest domain. Var is the selected variable from List, Rest is the rest of the list without Var.

deleteffc(?Var, +List, -Rest)
This predicate is used to select the most constrained variable from a list of domain variables. Var is the selected variable from List which has the least domain and which has the most constraints attached to it. Rest is the rest of the list without Var.

deletemin(?Var, +List, -Rest)
This predicate is used to select the domain variable with the smallest lower domain bound from a list of domain variables. Var is the selected variable from List, Rest is the rest of the list without Var.

List is a list of domain variables or integers. Integers are treated as if they were variables with singleton domains.

dom(+DVar, -List)
List is the list of elements in the domain of the domain variable DVar. The predicate ::/2 can also be used to query the domain of a domain variable, however it yields a list of intervals.

NOTE: This predicate should not be used in ECLiPSe programs, because all intervals in the domain will be expanded into element lists which causes unnecessary space and time overhead. Unless an explicit list representation is required, finite domains should be processed by the family of the dom_* predicates in sections 2.14.2 and 2.14.3.

maxdomain(+DVar, -Max)
Max is the maximum value in the domain of the integer domain variable DVar.

mindomain(+DVar, -Min)
Min is the minimum value in the domain of the integer domain variable DVar.

2.7  Utility Constraints Predicates

These constraints are defined in the module fd_util and they consist of useful predicates that are often needed in constraint programs. Their source code is available in the file fd_util.pl.
#(?Min, ?CstList, ?Max)
The cardinality operator. CstList is a list of constraint expressions and this operator states that at least Min and at most Max out of them are valid.

dvar_domain_list(?Var, ?List)
List is the list of elements in the domain of the domain variable or ground term DVar. The predicate ::/2 can also be used to query the domain of a domain variable, however it yields a list of intervals.

outof(?Var, +List)
The domain variable Var is different from all elements of the list List.

labeling(+List)
The elements of the List are instantiated using the indomain/1 predicate.

2.8  Search Methods

A library of different search methods for finite domain problems is available as library(fd_search). See the Reference Manual for details.

2.9  Domain Output

The library fd_domain.pl contains output macros which cause an fd attribute as well as a domain to be printed as lists that represent the domain values. A domain variable is an attributed variable whose fd attribute has a print handler which prints it in the same format. For instance,
[eclipse 4]: X::1..10, dvar_attribute(X, A), A = fd{domain:D}.

X = X{[1..10]}
D = [1..10]
A = [1..10]
yes.
[eclipse 5]: A::1..10, printf("%mw", A).
A{[1..10]}
A = A{[1..10]}
yes.

2.10  Debugging Constraint Programs

The ECLiPSe debugger is a low-level debugger which is suitable only to debug small constraint programs or to debug small parts of larger programs. Typically, one would use this debugger to debug user-defined constraints and Prolog data processing. When they are known to work properly, this debugger may not be helpful enough to find bugs (correctness debugging) or to speed up a working program (performance debugging). For this, the display_matrix tool from tkeclipse may be the appropriate tool.

2.11  Debugger Support

The ECLiPSe debugger supports debugging and tracing of finite domain programs in various ways. First of all, the debugger commands that handle suspended goals can be used to display suspended constraints (d, ^, u) or to skip to a particular constraint (w, i). Note that most of the constraints are displayed using a write macro, their internal form is different.

Successive updates of a domain variable can be traced using the debug event Hd. When used, the debugger prompts for a variable name and then it skips to the port at which the domain of this variable was reduced. When a newline is typed instead of a variable name, it skips to the update of the previously entered variable.

A sequence of woken goals can be skipped using the debug event Hw.

2.12  Examples

A very simple example of using the finite domains is the send more money puzzle:

:- use_module(library(fd)).

send(List) :-
    List = [S, E, N, D, M, O, R, Y],
    List :: 0..9,
    alldifferent(List),
    1000*S+100*E+10*N+D + 1000*M+100*O+10*R+E #=
        10000*M+1000*O+100*N+10*E+Y,
    M #\= 0,
    S #\= 0,
    labeling(List).
The problem is stated very simply, one just writes down the conditions that must hold for the involved variables and then uses the default labeling procedure, i.e. the order in which the variables will be instantiated. When executing send/1, the variables S, M and O are instantiated even before the labeling procedure starts. When a consistent value for the variable E is found (5), and this value is propagated to the other variables, all variables become instantiated and thus the rest of the labeling procedure only checks groundness of the list.

A slightly more elaborate example is the eight queens puzzle. Let us show a solution for this problem generalised to N queens and also enhanced by a cost function that evaluates every solution. The cost can be for example coli - rowi for the i-th queen. We are now looking for the solution with the smallest cost, i.e. one for which the maximum of all coli - rowi is minimal:
:- use_module(library(fd)).

% Find the minimal solution for the N-queens problem
cqueens(N, List) :-
    make_list(N, List),
    List :: 1..N,
    constrain_queens(List),
    make_cost(1, List, C),
    min_max(labeling(List), C).

% Set up the constraints for the queens
constrain_queens([]).
constrain_queens([X|Y]) :-
    safe(X, Y, 1),
    constrain_queens(Y).

safe(_, [], _).
safe(X, [Y|T], K) :-
    noattack(X, Y, K) ,
    K1 is K + 1 ,
    safe(X, T, K1).

% Queens in rows X and Y cannot attack each other
noattack(X, Y, K) :-
    X #\= Y,
    X + K #\= Y,
    X - K #\= Y.

% Create a list with N variables
make_list(0, []) :- !.
make_list(N, [_|Rest]) :-
    N1 is N - 1,
    make_list(N1, Rest).

% Set up the cost expression
make_cost(_, [], []).
make_cost(N, [Var|L], [N-Var|Term]) :-
    N1 is N + 1,
    make_cost(N1, L, Term).

labeling([]) :- !.
labeling(L) :-
    deleteff(Var, L, Rest),
    indomain(Var),
    labeling(Rest).
The approach is similar to the previous example: first we create the domain variables, one for each column of the board, whose values will be the rows. We state constraints which must hold between every pair of queens and finally we make the cost term in the format required for the min_max/2 predicate. The labeling predicate selects the most constrained variable for instantiation using the deleteff/3 predicate. When running the example, we get the following result:
[eclipse 19]: cqueens(8, X).
Found a solution with cost 5
Found a solution with cost 4

X = [5, 3, 1, 7, 2, 8, 6, 4] 
yes.
The time needed to find the minimal solution is about five times shorter than the time to generate all solutions. This shows the advantage of the branch and bound method. Note also that the board for this `minimal' solution looks very nice.

2.13  General Guidelines to the Use of Domains

The send more money example already shows the general principle of solving problems using finite domain constraints: The complexity of the program and the efficiency of the solving depends very much on the way these three points are performed. Quite frequently it is possible to state the same problem using different sets of variables with different domains. A guideline is that the search space should be as small as possible, and thus e.g. five variables with domain 1..10 (i.e. search space size is 105) are likely to be better than twenty variables with domain 0..1 (space size 220).

The choice of constraints is also very important. Sometimes a redundant constraint, i.e. one that follows from the other constraints, can speed up the search considerably. This is because the system does not propagate all information it has to all concerned variables, because most of the time this would not bring anything, and thus it would slow down the search. Another reason is that the library performs no meta-level reasoning on constraints themselves (unlike the CHR library). For example, the constraints
X + Y #= 10, X + Y + Z #= 14
allow only the value 4 for Z, however the system is not able to deduce this and thus it has to be provided as a redundant constraint.

The constraints should be stated in such a way that allows the system to propagate all important domain updates to the appropriate variables.

Another rule of thumb is that creation of choice points should be delayed as long as possible. Disjunctive constraints, if there are any, should be postponed as much as possible. Labeling, i.e. value choosing, should be done after all deterministic operations are carried out.

The choice of the labeling procedure is perhaps the most sensitive one. It is quite common that only a very minor change in the order of instantiated variables can speed up or slow down the search by several orders of magnitude. There are very few common rules available. If the search space is large, it usually pays off to spend more time in selecting the next variable to instantiate. The provided predicates deleteff/3 and deleteffc/3 can be used to select the most constrained variable, but in many problems it is possible to extract even more information about which variable to instantiate next.

Often it is necessary to try out several approaches and see how they work, if they do. The profiler and the statistics package can be of a great help here, it can point to predicates which are executed too often, or choice points unnecessarily backtracked over.

2.14  User-Defined Constraints

The fd.pl library defines a set of low-level predicates which allow the user to process domain variables and their domains, modify them and write new constraint predicates.

2.14.1  The fd Attribute

A domain variable is a metaterm. The fd.pl library defines a metaterm attribute
fd{domain:D, min:Mi, max:Ma, any:A}
which stores the domain information together with several suspension lists. The attribute arguments have the following meaning: The suspension list names can be used in the predicate suspend/3 to denote an appropriate waking condition.

The attribute of a domain variable can be accessed with the predicate dvar_attribute/2 or by unification in a matching clause:
get_attribute(_{fd:Attr}, A) :-
    -?->
    Attr = A.
Note however, that this matching clause succeeds even if the first argument is a metaterm but its fd attribute is empty. To succeed only for domain variables, the clause must be
get_attribute(_{fd:Attr}, A) :-
    -?->
    nonvar(Attr),
    Attr = A.
or to access directly attribute arguments, e.g. the domain
get_domain(_{fd:fd{domain:D}}, Dom) :-
    -?->
    D = Dom.
The dvar_attribute/2 has the advantage that it returns an attribute-like structure even if its argument is already instantiated, which is quite useful when coding fd constraints.

The attribute arguments can be accessed by macros from the structures.pl library, if e.g. Attr is the attribute of a domain variable, the max list can be obtained as
arg(max of fd, Attr, Max)
or, using a unification
Attr = fd{max:Max}

2.14.2  Domain Access

The domains are represented as abstract data types, the users are not supposed to access them directly, instead a number of predicates and macros are available to allow operations on domains.
dom_check_in(+Element, +Dom)
Succeed if the integer Element is in the domain Dom.

dom_compare(?Res, +Dom1, +Dom2)
Works like compare/3 for terms. Res is unified with Fails if neither domain is a subset of the other one.

dom_member(?Element, +Dom)
Successively instantiate Element to the values in the domain Dom (similar to indomain/1).

dom_range(+Dom, ?Min, ?Max)
Return the minimum and maximum value in the integer domain Dom. Fails if Dom is a domain containing non-integer elements. This predicate can also be used to test if a given domain is integer or not.

dom_size(+Dom, ?Size)
Size is the number of elements in the domain Dom.

2.14.3  Domain Operations

The following predicates operate on domains alone, without modifying domain variables. Most of them return the size of the resulting domain which can be used to test if any modification was done.
dom_copy(+Dom1, -Dom2)
Dom2 is a copy of the domain Dom1. Since the updates are done in-place, two domain variables must not share the same physical domain and so when defining a new variable with an existing domain, the domain has to be copied first.

dom_difference(+Dom1, +Dom2, -DomDiff, ?Size)
The domain DomDifference is Dom1 \ Dom2 and Size is the number of its elements. Fails if Dom1 is a subset of Dom2.

dom_intersection(+Dom1, +Dom2, -DomInt, ?Size)
The domain DomInt is the intersection of domains Dom1 and Dom2 and Size is the number of its elements. Fails if the intersection is empty.

dom_union(+Dom1, +Dom2, -DomUnion, ?Size)
The domain DomUnion is the union of domains Dom1 and Dom2 and Size is the number of its elements. Note that the main use of the predicate is to yield the most specific generalisation of two domains, in the usual cases the domains become smaller, not bigger.

list_to_dom(+List, -Dom)
Convert a list of ground terms and integer intervals into a domain Dom. It does not have to be sorted and integers and intervals may overlap.

integer_list_to_dom(+List, -Dom)
Similar to list_to_dom/2 , but the input list should contain only integers and integer intervals and it should be sorted. This predicate will merge adjacent integers and intervals into larger intervals whenever possible. typically, this predicate should be used to convert a sorted list of integers into a finite domain. If the list is known to already contain proper intervals, sorted_list_to_dom/2 could be used instead.

sorted_list_to_dom(+List, -Dom)
Similar to list_to_dom/2, but the input list is assumed to be already in the correct format, i.e. sorted and with correct integer and interval values. No checking on the list contents is performed.

2.14.4  Accessing Domain Variables

The following predicates perform various operations:
dvar_attribute(+DVar, -Attrib)
Attrib is the attribute of the domain variable DVar. If DVar is instantiated, Attrib is bound to an attribute with a singleton domain and empty suspension lists.

dvar_domain(+DVar, -Dom)
Dom is the domain of the domain variable DVar. If DVar is instantiated, Dom is bound to a singleton domain.

var_fd(?Var, +Dom)
If Var is a free variable, it becomes a domain variable with the domain Dom and with empty suspension lists. The domain Dom is copied to make in-place updates logically sound. If Var is already a domain variable, its domain is intersected with the domain Dom. Fails if Var is not a variable.

dvar_msg(+DVar1, +DVar2, -MsgDVar)
MsgVar is a domain variable which is the most specific generalisation of domain variables or ground values Var1 and Var2.

2.14.5  Modifying Domain Variables

When the domain of a domain variable is reduced, some suspension lists stored in the attribute have to be scheduled and woken.

NOTE: In the fd.pl library the suspension lists are woken precisely when the event associated with the list occurs. Thus e.g. the min list is woken if and only if the minimum value of the variable's domain is changed, but it is not woken when the variable is instantiated to this minimum or when another element from the domain is removed. In this way, user-defined constraints can rely on the fact that when they are executed, the domain was updated in the expected way. On the other hand, user-defined constraints should also comply with this rule and they should take care not to wake lists when their waking condition did not occur. Most predicates in this section actually do all the work themselves so that the user predicates may ignore scheduling and waking completely.
dvar_remove_element(+DVar, +El)
The element El is removed from the domain of DVar and all concerned lists are woken. If the resulting domain is empty, this predicate fails. If it is a singleton, DVar is instantiated. If the domain does not contain the element, no updates are made.

dvar_remove_smaller(+DVar, +El)
Remove all elements in the domain of DVar which are smaller than the integer El and wake all concerned lists. If the resulting domain is empty, this predicate fails; if it is a singleton, DVar is instantiated.

dvar_remove_greater(+DVar, +El)
Remove all elements in the domain of DVar which are greater than the integer El and wake all concerned lists. If the resulting domain is empty, this predicate fails; if it is a singleton, DVar is instantiated.

dvar_update(+DVar, +NewDom)
If the size of the domain NewDom is 0, the predicate fails. If it is 1, the domain variable DVar is instantiated to the value in the domain. Otherwise, if the size of the new domain is smaller than the size of the domain variable's domain, the domain of DVar is replaced by NewDom, the appropriate suspension lists in its attribute are passed to the waking scheduler and so is the constrained list in the suspend attribute of the domain variable. If the size of the new domain is equal to the old one, no updates and no waking is done, i.e. this predicate does not check an explicit equality of both domains. If the size of the new domain is greater than the old one, an error is raised.

dvar_replace(+DVar, +NewDom)
This predicate is similar to dvar_update/2, but it does not propagate the changes, i.e. no waking is done. If the size of the new domain is 1, DVar is not instantiated, but it is given this singleton domain. This predicate is useful for local consistency checks.

2.15  Extensions

The fd.pl library can be used as a basis for further extensions. There are several hooks that make the interfacing easier:

2.16  Example of Defining a New Constraint

We will demonstrate creation of new constraints on the following example. To show that the constraints are not restricted to linear terms, we can take the constraint
X2 + Y2C.
Assuming that X and Y are domain variables, we would like to define such a predicate that will be woken as soon as one or both variables' domains are updated in such a way that would require updating the other variable's domain, i.e. updates that would propagate via this constraint. For simplicity we assume that X and Y are nonnegative. We will define the predicate sq(X, Y, C) which will implement this constraint:
:- use_module(library(fd)).

% A*A + B*B <= C
sq(A, B, C) :-
    dvar_domain(A, DomA),
    dvar_domain(B, DomB),
    dom_range(DomA, MinA, MaxA),
    dom_range(DomB, MinB, MaxB),
    MiA2 is MinA*MinA,
    MaB2 is MaxB*MaxB,
    (MiA2 + MaB2 > C ->
        NewMaxB is fix(sqrt(C - MiA2)),
        dvar_remove_greater(B, NewMaxB)
    ;
        NewMaxB = MaxB
    ),
    MaA2 is MaxA*MaxA,
    MiB2 is MinB*MinB,
    (MaA2 + MiB2 > C ->
        NewMaxA is fix(sqrt(C - MiB2)),
        dvar_remove_greater(A, NewMaxA)
    ;
        NewMaxA = MaxA
    ),
    (NewMaxA*NewMaxA + NewMaxB*NewMaxB =< C ->
        true
    ;
        suspend(sq(A, B, C), 3, (A, B)->min)
    ),
    wake.                % Trigger the propagation
The steps to be executed when this constraint becomes active, i.e. when the predicate sq/3 is called or woken are the following:
  1. We access the domains of the two variables using the predicate dvar_domain/2 and and obtain their bounds using dom_range/3. Note that it may happen that one of the two variables is already instantiated, but these predicates still work as if the variable had a singleton domain.

  2. We check if the maximum of one or the other variable is still consistent with this constraint, i.e. if there is a value in the other variable's domain that satisfies the constraint together with this maximum.

  3. If the maximum value is no longer consistent, we compute the new maximum of the domain, and then update the domain so that all values greater than this value are removed using the predicate dvar_remove_greater/2. This predicate also wakes all concerned suspension lists and instantiates the variable if its new domain is a singleton.

  4. After checking the updates for both variables we test if the constraint is now satisfied for all values in the new domains. If this is not the case, we have to suspend the predicate so that it is woken as soon as the minimum of either domain is changed. This is done using the predicate suspend/3.

  5. The last action is to trigger the execution of all goals that are waiting for the updates we have made. It is necessary to wake these goals after inserting the new suspension, otherwise updates made in the woken goals would not be propagated back to this constraint.
Here is what we get:
[eclipse 20]: [X,Y]::1..10, sq(X, Y, 50).

X = X{[1..7]}
Y = Y{[1..7]}

Delayed goals:
 sq(X{[1..7]}, Y{[1..7]}, 50)
yes.
[eclipse 21]: [X,Y]::1..10, sq(X, Y, 50), X #> 5.

Y = Y{[1..3]}
X = X{[6, 7]}

Delayed goals:
 sq(X{[6, 7]}, Y{[1..3]}, 50)
yes.
[eclipse 22]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 1.

X = 6
Y = Y{[2, 3]}
yes.
[eclipse 23]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 2.

X = 6
Y = 3
yes.

2.17  Program Examples

In this section we present some FD programs that show various aspects of the library usage.

2.17.1  Constraining Variable Pairs

The finite domain library gives the user the possibility to impose constraints on the value of a variable. How, in general, is it possible to impose constraints on two or more variables? For example, let us assume that we have a set of colours and we want to define that some colours fit with each other and others do not. This should work in such a way as to propagate possible changes in the domains as soon as this becomes possible.

Let us assume we have a symmetric relation that defines which colours fit with each other:
% The basic relation
fit(yellow, blue).
fit(yellow, red).
fit(blue, yellow).
fit(red, yellow).
fit(green, orange).
fit(orange, green).
The predicate nice_pair(X, Y) is a constraint and any change of the possible values of X or Y is propagated to the other variable. There are many ways in which this pairing can be defined in ECLiPSe. They are different solutions with different properties, but they yield the same results.

2.17.1.1  User-Defined Constraints

We use more or less directly the low-level primitives to handle finite domain variables. We collect all consistent values for the two variables, remove all other values from their domains and then suspend the predicate until one of its arguments is updated:
nice_pair(A, B) :-
        % get the domains of both variables
    dvar_domain(A, DA),         
    dvar_domain(B, DB),         
        % make a list of respective matching colours
    setof(Y, X^(dom_member(X, DA), fit(X, Y)), BL),
    setof(X, Y^(dom_member(Y, DB), fit(X, Y)), AL),
        % convert the lists to domains
    sorted_list_to_dom(AL, DA1),
    sorted_list_to_dom(BL, DB1),
        % intersect the lists with the original domains
    dom_intersection(DA, DA1, DA_New, _),
    dom_intersection(DB, DB1, DB_New, _),
        % and impose the result on the variables
    dvar_update(A, DA_New),
    dvar_update(B, DB_New),
        % unless one variable is already instantiated, suspend
        % and wake as soon as any element of the domain is removed
    (var(A), var(B) ->
        suspend(nice_pair(A, B), 2, [A,B]->any)
    ;
        true
    ).

% Declare the domains
colour(A) :-
    findall(X, fit(X, _), L),
    A :: L.
After defining the domains, we can state the constraints:
[eclipse 5]: colour([A,B,C]), nice_pair(A, B), nice_pair(B, C), A #\= green.

B = B{[blue, green, red, yellow]}
C = C{[blue, orange, red, yellow]}
A = A{[blue, orange, red, yellow]}
 
Delayed goals:
  nice_pair(A{[blue, orange, red, yellow]}, B{[blue, green, red, yellow]})
  nice_pair(B{[blue, green, red, yellow]}, C{[blue, orange, red, yellow]})
This way of defining new constraints is often the most efficient one, but usually also the most tedious one.

2.17.1.2  Using the element Constraint

In this case we use the available primitive in the fd library. Whenever it is necessary to associate a fd variable with some other fd variable, the element/3 constraint is a likely candidate. Sometimes it is rather awkward to use, because additional variables must be used, but it gives enough power:
nice_pair(A, B) :-
    element(I, [yellow, yellow, blue, red, green, orange], A),
    element(I, [blue, red, yellow, yellow, orange, green], B).
We define a new variable I which is a sort of index into the clauses of the fit predicate. The first colour list contains colours in the first argument of fit/2 and the second list contains colours from the second argument. The propagation is similar to that of the previous one.

When element/3 can be used, it is usually faster than the previous approach, because element/3 is partly implemented in C.

2.17.1.3  Using Evaluation Constraints

We can also encode directly the relations between elements in the domains of the two variables:
nice_pair(A, B) :-
    np(A, B),
    np(B, A).

np(A, B) :-
    [A,B] :: [yellow, blue, red, orange, green],
    A #= yellow #=> B :: [blue, red],
    A #= blue #=> B #= yellow,
    A #= red #=> B #= yellow,
    A #= green #=> B #= orange,
    A #= orange #=> B #= green.
This method is quite simple and does not need any special analysis; on the other hand it potentially creates a huge number of auxiliary constraints and variables.

2.17.1.4  Using Generalised Propagation

Propia is the first candidate to convert an existing relation into a constraint. One can simply use infers most to achieve the propagation:
nice_pair(A, B) :-
    fit(A, B) infers most.
Using Propia is usually very easy and the programs are short and readable, so that this style of constraints writing is quite useful e.g. for teaching. It is not as efficient as with user-defined constraints, but if the amount of propagation is more important that the efficiency of the constraint itself, it can yield good results, too.

2.17.1.5  Using Constraint Handling Rules

The domain solver in CHR can be used directly with the element/3 constraint as well, however it is also possible to define directly domains consisting of pairs:
:- lib(chr).
:- chr(lib(domain)).

nice_pair(A, B) :-
    setof(X-Y, fit(X, Y), L),
    A-B :: L.

The pairs are then constrained accordingly:
[eclipse 2]: nice_pair(A, B), nice_pair(B, C), A ne orange.

B = B
C = C
A = A

Constraints:
(9) A_g1484 - B_g1516 :: [blue - yellow, green - orange, red - yellow,
yellow - blue, yellow - red]
(10) A_g1484 :: [blue, green, red, yellow]
(12) B_g1516 - C_g3730 :: [blue - yellow, orange - green, red - yellow,
yellow - blue, yellow - red]
(13) B_g1516 :: [blue, orange, red, yellow]
(14) C_g3730 :: [blue, green, red, yellow]

2.17.2  Puzzles

Various kinds of puzzles can be easily solved using finite domains. We show here the classical Lewis Carrol's puzzle with five houses and a zebra:
Five men with different nationalities live in the first five houses
of a street.  They practise five distinct professions, and each of
them has a favourite animal and a favourite drink, all of them
different.  The five houses are painted in different colours.

The Englishman lives in a red house.
The Spaniard owns a dog.
The Japanese is a painter.
The Italian drinks tea.
The Norwegian lives in the first house on the left.
The owner of the green house drinks coffee.
The green house is on the right of the white one.
The sculptor breeds snails.
The diplomat lives in the yellow house.
Milk is drunk in the middle house.
The Norwegian's house is next to the blue one.
The violinist drinks fruit juice.
The fox is in a house next to that of the doctor.
The horse is in a house next to that of the diplomat.

Who owns a Zebra, and who drinks water?
One may be tempted to define five variables Nationality, Profession, Colour, etc. with atomic domains to represent the problem. Then, however, it is quite difficult to express equalities over these different domains. A much simpler solution is to define 5x5 integer variables for each mentioned item, to number the houses from one to five and to represent the fact that e.g. Italian drinks tea by equating Italian = Tea. The value of both variables represents then the number of their house. In this way, no special constraints are needed and the problem is very easily described:
:- lib(fd).

zebra([zebra(Zebra), water(Water)]) :-
    Sol = [Nat, Color, Profession, Pet, Drink],
    Nat = [English, Spaniard, Japanese, Italian, Norwegian],
    Color = [Red, Green, White, Yellow, Blue],
    Profession = [Painter, Sculptor, Diplomat, Violinist, Doctor],
    Pet = [Dog, Snails, Fox, Horse, Zebra],
    Drink = [Tea, Coffee, Milk, Juice, Water],

    % we specify the domains and the fact
    % that the values are exclusive
    Nat :: 1..5,
    Color :: 1..5,
    Profession :: 1..5,
    Pet :: 1..5,
    Drink :: 1..5,
    alldifferent(Nat),
    alldifferent(Color),
    alldifferent(Profession),
    alldifferent(Pet),
    alldifferent(Drink),

    % and here follow the actual constraints
    English = Red,
    Spaniard = Dog,
    Japanese = Painter,
    Italian = Tea,
    Norwegian = 1,
    Green = Coffee,
    Green #= White + 1,
    Sculptor = Snails,
    Diplomat = Yellow,
    Milk = 3,
    Dist1 #= Norwegian - Blue, Dist1 :: [-1, 1],
    Violinist = Juice,
    Dist2 #= Fox - Doctor, Dist2 :: [-1, 1],
    Dist3 #= Horse - Diplomat, Dist3 :: [-1, 1],

    flatten(Sol, List),
    labeling(List).

2.17.3  Bin Packing

In this type of problems the goal is to pack a certain amount of different things into the minimal number of bins under specific constraints. Let us solve an example given by Andre Vellino in the Usenet group comp.lang.prolog, June 93: To solve this problem, it is not enough to state constraints on some variables and to start a labeling procedure on them. The variables are namely not known, because we don't know how many bins we should take. One possibility would be to take a large enough number of bins and to try to find a minimum number. However, usually it is better to generate constraints for an increasing fixed number of bins until a solution is found.

The predicate solve/1 returns the solution for this particular problem, solve_bin/2 is the general predicate that takes an amount of components packed into a cont/5 structure and it returns the solution.
solve(Bins) :-
    solve_bin(cont(1, 2, 1, 3, 2), Bins).
solve_bin/2 computes the sum of all components which is necessary as a limit value for various domains, calls bins/4 to generate a list Bins with an increasing number of elements and finally it labels all variables in the list:
solve_bin(Demand, Bins) :-
    Demand = cont(G, P, S, W, C),
    Sum is G + P + S + W + C,
    bins(Demand, Sum, [Sum, Sum, Sum, Sum, Sum, Sum], Bins),
    label(Bins).
The predicate to generate a list of bins with appropriate constraints works as follows: first it tries to match the amount of remaining components with zero and the list with nil. If this fails, a new bin represented by a list
[Colour, Glass, Plastic, Steel, Wood, Copper]
is added to the bin list, appropriate constraints are imposed on all the new bin's variables, its contents is subtracted from the remaining number of components, and the predicate calls itself recursively:
bins(cont(0, 0, 0, 0, 0), 0, _, []).
bins(cont(G0, P0, S0, W0, C0), Sum0, LastBin, [Bin|Bins]) :-
    Bin = [_Col, G, P, S, W, C],
    bin(Bin, Sum),
    G2 #= G0 - G,
    P2 #= P0 - P,
    S2 #= S0 - S,
    W2 #= W0 - W,
    C2 #= C0 - C,
    Sum2 #= Sum0 - Sum,
    ordering(Bin, LastBin),
    bins(cont(G2, P2, S2, W2, C2), Sum2, Bin, Bins).
The ordering/2 constraints are strictly necessary because this problem has a huge number of symmetric solutions.

The constraints imposed on a single bin correspond exactly to the problem statement:
bin([Col, G, P, S, W, C], Sum) :-
    Col :: [red, blue, green],
    [Capacity, G, P, S, W, C] :: 0..4,
    G + P + S + W + C #= Sum,
    Sum #> 0,               % no empty bins
    Sum #<= Capacity,
    capacity(Col, Capacity),
    contents(Col, G, P, S, W, C),
    requires(W, P),
    exclusive(G, C),
    exclusive(C, P),
    at_most(1, red, Col, W),
    at_most(2, green, Col, W).
We will code all of the special constraints with the maximum amount of propagation to show how this can be achieved. In most programs, however, it is not necessary to propagate all values everywhere which simplifies the code quite considerably. Often it is also possible to use some of the built-in symbolic constraints of ECLiPSe, e.g. element/3 or atmost/3.

2.17.3.1  Capacity Constraints

capacity(Color, Capacity) should instantiate the capacity if the colour is known, and reduce the colour values if the capacity is known to be greater than some values. If we use evaluation constraints, we can code the constraint directly, using equivalences:
capacity(Color, Capacity) :-
    Color #= blue #<=> Capacity #= 1,
    Color #= green #<=> Capacity #= 4,
    Color #= red #<=> Capacity #= 3.
A more efficient code would take into account the ordering on the capacities. Concretely, if the capacity is greater than 1, the colour cannot be blue and if it is greater than 3, it must be green:
capacity(Color, Capacity) :-
    var(Color),
    !,
    dvar_domain(Capacity, DC),
    dom_range(DC, MinC, _),
    (MinC > 1 ->
        Color #\= blue,
        (MinC > 3 ->
            Color = green
        ;
            suspend(capacity(Color, Capacity), 3, (Color, Capacity)->inst)
        )
    ;
        suspend(capacity(Color, Capacity), 3, [Color->inst, Capacity->min])
    ).
capacity(blue, 1).
capacity(green, 4).
capacity(red, 3).
Note that when suspended, the predicate waits for colour instantiation or for minimum of the capacity to be updated (except that 3 is one less than the maximum capacity and thus waiting for its instantiation is equivalent).

2.17.3.2  Containment Constraints

The containment constraints are stated as logical expressions and this is also the easiest way to medel them. The important point to remember is that a condition like red can contain glass, wood, copper actually means red cannot contain plastic or steel which can be written as
contents(Col, G, P, S, W, _) :-
    Col #= red #=> P #= 0 #/\ S #= 0,
    Col #= blue #=> P #= 0 #/\ W #= 0,
    Col #= green #=> G #= 0 #/\ S #= 0.
If we want to model the containment with low-level domain predicates, it is easier to state them in the equivalent conjugate form: or in a further equivalent form that uses at most one bin colour:
contents(Col, G, P, S, W, _) :-
    not_contained_in(Col, G, green),
    contained_in(Col, P, green),
    contained_in(Col, S, blue),
    not_contained_in(Col, W, blue).
contained_in(Color, Component, In) states that if Color is different from In, there can be no such component in it, i.e. Component is zero:
contained_in(Col, Comp, In) :-
    nonvar(Col),
    !,
    (Col \== In ->
        Comp = 0
    ;
        true
    ).
contained_in(Col, Comp, In) :-
    dvar_domain(Comp, DM),
    dom_range(DM, MinD, _),
    (MinD > 0 ->
        Col = In
    ;
        suspend(contained_in(Col, Comp, In), 2, [Comp->min, Col->inst])
    ).
not_contained_in(Color, Component, In) states that if the bin is of the given colour, the component cannot be contained in it:
not_contained_in(Col, Comp, In) :-
    nonvar(Col),
    !,
    (Col == In ->
        Comp = 0
    ;
        true
    ).
not_contained_in(Col, Comp, In) :-
    dvar_domain(Comp, DM),
    dom_range(DM, MinD, _),
    (MinD > 0 ->
        Col #\= In
    ;
        suspend(not_contained_in(Col, Comp, In), 2, [Comp->min, Col->any])
    ).
As you can see again, modeling with the low-level domain predicates might give a faster and more precise programs, but it is much more difficult than using constraint expressions and evaluation constraints. A good approach is thus to start with constraint expressions and only if they are not efficient enough, to (stepwise) recode some or all constraints with the low-level predicates.

2.17.3.3  Requirement Constraints

The constraint `A requires B' is written as
requires(A, B) :-
    A #> 0 #=> B #> 0.
With low-level predicates, the constraint `A requires B' is woken as soon as some A is present or B is known:
requires(A, B) :-
    nonvar(B),
    !,
    ( B = 0 ->
        A = 0
    ;
        true
    ).
requires(A, B) :-
    dvar_domain(A, DA),
    dom_range(DA, MinA, _),
    ( MinA > 0 ->
        B #> 0
    ;
        suspend(requires(A, B), 2, [A->min, B->inst])
    ).

2.17.3.4  Exclusive Constraints

The exclusive constraint can be written as
exclusive(A, B) :-
    A #> 0 #=> B #= 0,
    B #> 0 #=> A #= 0.
however a simple form with one disjunction is enough:
exclusive(A, B) :-
    A #= 0 #\/ B #= 0.
With low-level domain predicates, the exclusive constraint defines a suspension which is woken as soon as one of the two components is present:
exclusive(A, B) :-
    dvar_domain(A, DA),
    dom_range(DA, MinA, MaxA),
    ( MinA > 0 ->
        B = 0
    ; MaxA = 0 ->
        % A == 0
        true
    ;
        dvar_domain(B, DB),
        dom_range(DB, MinB, MaxB),
        ( MinB > 0 ->
            A = 0
        ; MaxB = 0 ->
            % B == 0
            true
        ;
            suspend(exclusive(A, B), 3, (A,B)->min)
        )
    ).

2.17.3.5  Atmost Constraints

at_most(N, In, Colour, Components) states that if Colour is equal to In, then there can be at most N Components and vice versa, if there are more than N Components, the colour cannot be In. With constraint expressions, this can be simply coded as
at_most(N, In, Col, Comp) :-
    Col #= In #=> Comp #<= N.
A low-level solution looks as follows:
at_most(N, In, Col, Comp) :-
    nonvar(Col),
    !,
    (In = Col ->
        Comp #<= N
    ;
        true
    ).
at_most(N, In, Col, Comp) :-
    dvar_domain(Comp, DM),
    dom_range(DM, MinM, _),
    (MinM > N ->
        Col #\= In
    ;
        suspend(at_most(N, In, Col, Comp), 2, [In->inst, Comp->min])
    ).

2.17.3.6  Ordering Constraints

To filter out symmetric solutions we can e.g. impose a lexicographic ordering on the bins in the list, i.e. the second bin must be lexicographically greater or equal than the first one etc. As long as the corresponding most significant variables in two consecutive bins are not instantiated, we cannot constrain the following ones and thus we suspend the ordering on the inst lists:
ordering([], []).
ordering([Val1|Bin1], [Val2|Bin2]) :-
    Val1 #<= Val2,
    (integer(Val1) ->
        (integer(Val2) ->
            (Val1 = Val2 ->
                ordering(Bin1, Bin2)
            ;
                true
            )
        ;
            suspend(ordering([Val1|Bin1], [Val2|Bin2]), 2, Val2->inst)
        )
    ;
        suspend(ordering([Val1|Bin1], [Val2|Bin2]), 2, Val1->inst)
    ).
There is a problem with the representation of the colour: If the colour is represented by an atom, we cannot apply the #<=/2 predicate on it. To keep the ordering predicate simple and still have a symbolic representation of the colour in the program, we can define input macros that transform the colour atoms into integers:
:- define_macro(no_macro_expansion(blue)/0, tr_col/2, []).
:- define_macro(no_macro_expansion(green)/0, tr_col/2, []).
:- define_macro(no_macro_expansion(red)/0, tr_col/2, []).

tr_col(no_macro_expansion(red), 1).
tr_col(no_macro_expansion(green), 2).
tr_col(no_macro_expansion(blue), 3).

2.17.3.7  Labeling

A straightforward labeling would be to flatten the list with the bins and use e.g. deleteff/3 to label a variable out of it. However, for this example not all variables have the same importance — the colour variables propagate much more data when instantiated. Therefore, we first filter out the colours and label them before all the component variables:
label(Bins) :-
    colours(Bins, Colors, Things),
    flatten(Things, List),
    labeleff(Colors),
    labeleff(List).

colours([], [], []).
colours([[Col|Rest]|Bins], [Col|Cols], [Rest|Things]) :-
    colours(Bins, Cols, Things).

labeleff([]).
labeleff(L) :-
    deleteff(V, L, Rest),
    indomain(V),
    labeleff(Rest).
Note also that we need a special version of flatten/3 that works with nonground lists.

2.18  Current Known Restrictions and Bugs

  1. The default domain for integer finite domain variables is -10000000..10000000. Larger domains must be stated explicitly using the ::/2 predicate, however neither bound can be outside the standard integer range for the machine (usually 32 bits).

  2. Linear integer terms are processed using machine integers and thus if the maximum or minimum value of a linear term overflows this range (usually 32 bits), incorrect results are reported. This may occur if large coefficients are used, if domains are too large or a combination of the two.

Previous Up Next