SWI-Prolog 5.5.14 Reference Manual: Section A.8

A.8 library( clp/bounds ): Integer Bounds Constraint Solver

Author: Tom Schrijvers, K.U.Leuven

The bounds solver is a rather simple integer constraint solver, implemented with attributed variables. Its syntax is a subset of the SICStus clp(FD) syntax. Please note that the library(clp/bounds) library is not an autoload library and therefore this library must be loaded explicitely before using it using:

:- use_module(library('clp/bounds')).

A.8.1 Constraints

The following constraints are supported:

-Var in +Range: Varibale Var is restricted to be in rage Range. A range is denoted by L..U where both L and U are integers.
-Vars in +Range: A list of variables Vars are restriced to be in range Range.
?Expr #> ?Expr: The left-hand expression is constrained to be greater than the right-hand expressions.
?Expr #< ?Expr: The left-hand expression is constrained to be smaller than the right-hand expressions.
?Expr #>= ?Expr: The left-hand expression is constrained to be greater than or equal to the right-hand expressions.
?Expr #=< ?Expr: The left-hand expression is constrained to be smaller than or equal to the right-hand expressions.
?Expr #= ?Expr: The left-hand expression is constrained to be equal to the right-hand expressions.
?Expr #\= ?Expr: The left-hand expression is constrained to be not equal to the right-hand expressions.
sum(+Vars,+Op,?Value): Here Vars is a list of variables and integers, Op is one of the binary constraint relation symbols above and Value is an integer or variable. It represents the constraint (ΣVars) Op Value.
lex_chain(+VarsLists): The constraint enforces lexicographic ordering on the lists in the argument. The argument Vars is a list of lists of variables and integers. The current implementation was contributed by Markus Triska.
all_different(+Vars): Constrains all variabls in the list Vars to be pairwise not equal.
indomain(+Var): Assigns a value in its domain to variable Var. Backtracks over all possible values from lowest to greatest. Contributed by Markus Triska.
label(+Vars): All variables are assigned a variable that does not violate the constraint on them.

Here Expr can be one of

integer: Any integer.
variable: A variable.
?Expr + ?Expr: The sum of two expressions.
?Expr * ?Expr: The product of two expressions.
?Expr - ?Expr: The difference of two expressions.
max(?Expr,?Expr): The maximum of two expressions.
min(?Expr,?Expr): The minimum of two expressions.
?Expr mod ?Expr: The first expression modulo the second expression.
abs(?Expr): The absolute value of an expression.

A.8.2 Constraint Implication and Reified Constraints

The following constraint implication predicates are available:

+P #=> +Q: P implies Q, where P and Q are reifyable constraints.
+Q #<= +P: P implies Q, where P and Q are reifyable constraints.
+P #<=> +Q: P and Q are equivalent, where P and Q are reifyable constraints.

In addition, instead of being a reifyable constraint, either P or Q can be a boolean variable that is the truth value of the corresponding constraint.

The following constraints are reifyable: #=/2, #\=/2, #</2, #>/2, #=</2, #>/2.

For example, to count the number of occurrences of a particular value in a list of constraint variables:

Using constraint implication

occurrences(List,Value,Count) :- occurrences(List,Value,0,Count). occurrences([],_,Count,Count). occurrences([X|Xs],Value,Acc,Count) :- X #= Value #=> NAcc #= Acc + 1, X #\= Value #=> NAcc #= Acc, occurrences(Xs,Value,NAcc,Count).

Using reified constraints

occurrences(List,Value,Count) :- occurrences(List,Value,0,Count). occurrences([],_,Count,Count). occurrences([X|Xs],Value,Acc,Count) :- X #= Value #=> B, NAcc #= Acc + B, occurrences(Xs,Value,NAcc,Count).

A.8.3 Example

The following is an implementation of the classic alphametics puzzle SEND + MORE = MONEY:

:- use_module(library('clp/bounds')). send([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]) :- Digits = [S,E,N,D,M,O,R,Y], Carries = [C1,C2,C3,C4], Digits in 0..9, Carries in 0..1, M #= C4, O + 10 * C4 #= M + S + C3, N + 10 * C3 #= O + E + C2, E + 10 * C2 #= R + N + C1, Y + 10 * C1 #= E + D, M #>= 1, S #>= 1, all_different(Digits), label(Digits).

A.8.4 SICStus clp(FD) compatibility

Apart from the limited syntax, the bounds solver differs in the following ways from the SICStus clp(FD) solver:

inf and sup
The smallest lowerbound and greatest upperbound in bounds are max_integer and min_integer + 1.