14.3 Constraint Behaviours
As opposed to the theoretical CSP framework sketched in the previous section,
in ECL^{i}PS^{e} we usually deal with more heterogeneous situation.
We want to allow the integration of very different constraints,
and we want to achieve a separation of constraint propagation and search.
Therefore, we are not interested in an overall problem solving algorithm
which controls search and constraint propagation globally for the whole
problem and all constraints.
We prefer to view the constraint solving process as in figure 14.1:
the search process is controlled by an algorithmic program,
while constraint propagation is performed by datadriven agents which
do local (again algorithmic) computations on one or several constraints.
Figure 14.1: Control during Constraint Solving
Individual constraints can then be implemented with different behaviours,
and freely mixed within a single computation.
Constraint behaviours can essentially be characterised by

their triggering condition (when are they executed)
 the action they perform when triggered (what do they do)
Let us now look at examples of different constraint behaviours.
14.3.1 Consistency Check
The =<
/2 predicate, whose standard Prolog version raises an error
when invoked with uninstantiated variable, is also implemented by the
suspend library. Both implementations
have the same declarative meaning, but the suspend version can
be considered to be a proper constraint.
It implements a passive test, i.e.
it simply delays until both arguments are numbers, and then succeeds or fails:
? suspend : (X =< 4).
X = X
There is 1 delayed goal.
Yes (0.00s cpu)
? suspend : (X =< 4), X = 2.
X = 2
Yes (0.00s cpu)
? suspend : (X =< 4), X = 5.
No (0.00s cpu)
14.3.2 Forward Checking
Often a constraint can already do useful work before all its arguments
are instantiated. In particular, this is the case when we are working
with domain variables. Consider ic's disequality constraint #\=
:
Even when only one side is instantiated, it can already remove this value
from the domain of the other (still uninstantiated) side:
? X :: 1 .. 5,
X #\= 3.
X = X{[1, 2, 4, 5]}
Yes (0.00s cpu)
If both sides are uninstantiated, the constraint cannot do anything useful.
It therefore waits (delays) until one side becomes instantiated,
but then wakes up and acts as before.
This behaviour is sometimes called forward checking [27]:
? [X,Y] :: 1 .. 5,
X #\= Y. % delays
X = X{1 .. 5}
Y = Y{1 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)
? X :: 1 .. 5,
X #\= Y, % delays
Y = 3. % wakes
X = X{[1, 2, 4, 5]}
Y = 3
Yes (0.01s cpu)
14.3.3 Domain (Arc) Consistency
For many constraints, even more eager behaviour is possible.
For example, ic's inequality constraints performs domain updates as
soon as possible, even when one or both arguments are still variables:
? [X, Y] :: 1 .. 5, X #< Y.
X = X{1 .. 4}
Y = Y{2 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)
? [X, Y] :: 1 .. 5, X #< Y, X #> 2.
Y = Y{[4, 5]}
X = X{[3, 4]}
There is 1 delayed goal.
Yes (0.00s cpu)
Inconsistent values are removed form the domains as soon as possible.
This behaviour corresponds to arc consistency as discussed in
section 14.2.
14.3.4 Bounds Consistency
Note however that not all ic constraints maintain full domain
arc consistency. For performance reasons,
the #=
constraint only maintains bounds consistency, which is
weaker, as illustrated by the following example:
? [X, Y] :: 1 .. 5, X #= Y + 1, X #\= 3.
Y = Y{1 .. 4}
X = X{[2, 4, 5]}
There is 1 delayed goal.
Yes (0.00s cpu)
Here, the value 4 for Y was not removed even though it is not arc consistent
(there is no value for X which is compatible with it).
It is important to understand that this kind of propagation incompleteness
does not affect correctness: the constraint will simply detect the
inconsistency later, when its arguments have become more instantiated.
In terms of the search tree, this means that a branch will not be pruned
as early as possible, and extra time might be spent searching.

Consistency Checking

wait until all variables instantiated, then check
 Forward Checking

wait until one variable left, then compute consequences
 Domain (Arc) Consistency

wait until a domain changes, then compute consequences for other domains
 Bounds Consistency

wait until a domain bound changes, then compute consequences for other bounds

Figure 14.2: Typical Constraint Behaviours