4.1  Various Constraints over Lists and Arrays

The libraries ic_global and ic_global_gac implement a number of constraints over lists of integer variables. They are loaded using a directive like

:- use_module(library(ic_global)). % or :- lib(ic_global).

For details of the implemented constraints, refer to the Reference Manual for the libraries.

These constraints are commonly known as global constraints, which simply indicates that they can constrain a large number of variables at once, without breaking up the constraint into more primitive constraints. This can on one hand facilitate problem modelling, and on the other hand lead to more effective constraint propagation.

Note that some constraints are implemented in both of the libraries: in these cases, ic_global_gac implements a "globally arc consistent" version, while ic_global implements a less computationally expensive version with weaker propagation.

Among the constraints provided are the following (refer to the Reference Manual for the complete list):

alldifferent(+List)

A version of alldifferent/1 with strong propagation.

alldifferent(+List, ++Capacity)

Like alldifferent/1, but every value may occur Capacity times.

alldifferent_matrix(+Matrix)

Constrains the rows and columns of Matrix to be different values.

gcc(++Bounds,+Vars)

The global cardinality constraint makes sure certain values occur with a certain frequency in Vars. This is a generalisation of the occurrences-constraint. See also gcc_matrix/3.

inverse(+Succ, +Pred)

Constrains elements of Succ to be the successors and Pred to be the predecessors of nodes in a digraph.

lex_le(+List1, +List2)

Imposes a lexicographic ordering between the two lists.

lex_lt(+List1, +List2)

Imposes a strict lexicographic ordering between the two lists.

ordered(++Relation, +List)

Constrains List to be ordered according to Relation. Relation is one of the atoms <, =<, >, >=, = .

ordered_sum(++List, +Sum)

The list elements are ordered and their sum is Sum. A combination of ordered and sum constraint with stronger propagation.

occurrences(++Value, +List, ?N)

The value Value occurs in List N times. Operationally: N gets updated to reflect the number of possible occurrences in the List. List elements may get instantiated to Value, or Value may be removed from their domain if required by N.

same(+List1, +List2)

List2 is a permutation of List1.

sequence(+Low, +High, +K, +Vars, ++Values)

Every subsequence of Vars of length K contains at least Low and at most High occurrences of Values. Also sequence/4.

sorted(?List, ?Sorted)

Sorted is a sorted permutation of List.

sorted(?List, ?Sorted, ?Positions)

Sorted is a sorted permutation of List and Positions is a list whose elements indicating the position of each unsorted list element within the sorted list.

sumlist(+List, ?Sum)

The sum of the list elements is Sum. This constraint is more efficient than a general IC sum constraint if the list is long and Sum is not constrained frequently.