The solver contains predicates for checking the consistency and entailment of finite domain constraints, as well as solving for solution values for your problem variables.
In the context of this constraint solver, a finite domain is a subset of small integers, and a finite domain constraint denotes a relation over a tuple of small integers. Hence, only small integers and unbound variables are allowed in finite domain constraints.
All domain variables, i.e. variables that occur as
arguments to finite domain constraints get associated with a
finite domain, either explicitly declared by the program, or
implicitly imposed by the constraint solver. Temporarily, the domain of
a variable may actually be infinite, if it does not have a finite
lower or upper bound. If during the computation a variable receives a
new lower or upper bound that cannot be represented as a small
integer, an overflow condition is issued. This is expressed as silent
failure or as a representation error, subject to the overflow
option of fd_flag/3.
The domain of all variables gets smaller and smaller as more constraints are added. If a domain becomes empty, the accumulated constraints are unsatisfiable, and the current computation branch fails. At the end of a successful computation, all domains have usually become singletons, i.e. the domain variables have become assigned.
The domains do not become singletons automatically. Usually, it takes some amount of search to find an assignment that satisfies all constraints. It is the programmer's responsibility to do so. If some domain variables are left unassigned in a computation, the garbage collector will preserve all constraint data that is attached to them.
Please note: if a term containing domain variables is
written, copied, asserted, gathered as a solution to findall/3
and friends, or raised as an exception, those domain variables will be
replaced by brand new variables in the copy. To retain the domain
variables and any attached constraints, you can use copy_term/3
(see ref-lte-cpt). API change wrt. release 3.
The heart of the constraint solver is a scheduler for indexicals [Van Hentenryck et al. 92] and global constraints. Both entities act as coroutines performing incremental constraint solving or entailment checking. They wake up by changes in the domains of its arguments. All constraints provided by this package are implemented as indexicals or global constraints. New constraints can be defined by the user.
Indexicals are reactive functional rules, which take part in the solver's basic constraint solving algorithm, whereas each global constraint is associated with its particular constraint solving algorithm. The solver maintains two scheduling queues, giving priority to the queue of indexicals.
The feasibility of integrating the indexical approach with a Prolog based on the WAM was clearly demonstrated by Diaz's clp(FD) implementation [Diaz & Codognet 93], one of the fastest finite domains solvers around.