# Constraint programming over finite domains

Author(s): J.M. Gomez, M. Carro.

This package allows to write and evaluate constraint programming expressions over finite domains in a Ciao program. It is based upon the indexicals concept.

The syntax of this constraint system is described below:

• c ::= X in r (r is the range of variable X).
• c ::= E1 .=. E2 (eventual value of expression E1 equals E2)
• c ::= E1 .<>. E2 (E1 differs from E2)
• c ::= E1 .<. E2 (E1 is lower than E2)
• c ::= E1 .>. E2 (E1 is greater than E2)
• c ::= E1 .=<. E2 (E1 is lower or equal than E2)
• c ::= E1 .>=. E2 (E1 is greater or equal than E2)
• r ::= r1 (one interval range).
• r ::= r1 .&. r (multi interval range).
• r1 ::= t..t (interval range).
• r1 ::= dom(X) (indexical domain, e.g., X in dom(Y) means "X in the domain of Y").
• t::= n (integer).
• t::= min(X) (indexical min).
• t::= max(X) (indexical max).

Some examples of this constraints package (more can be found in the source and library directories):

• SEND + MORE = MONEY:

```:- use_package(fd).
:- use_module(library(prolog_sys), [statistics/2]).
:- use_module(library(format)).

smm(SMM) :-
statistics(runtime,_),
do_smm(SMM),
statistics(runtime,[_, Time]),
format("Used ~d milliseconds~n", Time).

do_smm(X) :-
X = [S,E,N,D,M,O,R,Y],
X in 0 .. 9,
all_different(X),
M .>. 0,
S .>. 0,
1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E .=. 10000*M + 1000*O + 100*N + 10*E + Y,
labeling(X).

```
• Queens:

```:- use_package(fd).
:- use_module(library(prolog_sys), [statistics/2]).
:- use_module(library(format)).
:- use_module(library(aggregates)).
:- use_module(library(lists),[length/2]).

queens(N, Qs) :-
statistics(runtime,_),
do_queens(N, Qs),
statistics(runtime,[_, Time]),
format("Used ~d milliseconds~n", Time).

do_queens(N, Qs):-
constrain_values(N, N, Qs),
all_different(Qs),!,
labeling(Qs).

constrain_values(0, _N, []).
constrain_values(N, Range, [X|Xs]):-
N > 0,
X in 1 .. Range,
N1 is N - 1,
constrain_values(N1, Range, Xs),
no_attack(Xs, X, 1).

no_attack([], _Queen, _Nb).
no_attack([Y|Ys], Queen, Nb):-
Nb1 is Nb + 1,
no_attack(Ys, Queen, Nb1),
Queen .<>. Y + Nb,
Queen .<>. Y - Nb.

```

## Usage and interface (`fd`)

• Library usage: `:- use_package(fd).` or `:- module(...,...,[fd]).`
• Exports:
• Predicates: `labeling/1`, `pitm/2`, `choose_var/3`, `choose_free_var/2`, `choose_var_nd/2`, `choose_value/2`, `retrieve_range/2`, `retrieve_store/2`, `glb/2`, `lub/2`, `bounds/3`, `retrieve_list_of_values/2`.
• Regular Types: `fd_item/1`, `fd_range/1`, `fd_subrange/1`, `fd_store/1`, `fd_store_entity/1`.
• New operators defined: `.=./2` [700,xfx], `.<>./2` [700,xfx], `.<./2` [700,xfx], `.=<./2` [700,xfx], `.>./2` [700,xfx], `.>=./2` [700,xfx], `../2` [500,yfx], `.@&./2` [600,xfy], `in/2` [700,xfy].

## Documentation on exports (`fd`)

REGTYPE: fd_item/1:

Usage: `fd_item(FD_item)`

• Description: `FD_item` is a finite domain entity, i.e. either a finite domains variable or an integer.

REGTYPE: fd_range/1:

Usage: `fd_range(FD_range)`

• Description: `FD_range` is the range of a finite domain entity.

REGTYPE: fd_subrange/1:

Usage:

• Description: A subrange is a pair representing a single interval.

REGTYPE: fd_store/1:

Usage: `fd_store(FD_store)`

• Description: `FD_store` is a representation of the constraint store of a finite domain entity.

REGTYPE: fd_store_entity/1:

Usage:

• Description: Representation of primitive constraints.

PREDICATE: labeling/1:

Usage: `labeling(Vars)`

• Description: Implements the labeling process. Assigns values to the input variables `Vars`. On exit all variables are instantiated to a consistent value. On backtracking, the predicate returns all possible assignments. No labeling heuristics implemented so far, i.e. variables are instantiated in their order of appearance.
• The following properties should hold at call time: `Vars` is a list of `fd_item`s. (`basic_props:list/2`)

PREDICATE: pitm/2:

Usage: `pitm(+V, -MiddlePoint)`

• Description: Returns in `MiddlePoint` the intermediate value of the range of `V`. In case `V` is a ground integer value the returned value is `V` itself.
• The following properties should hold at call time: `+V` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-MiddlePoint` is an integer. (`basic_props:int/1`)

PREDICATE: choose_var/3:

Usage: `choose_var(+ListOfVars, -Var, -RestOfVars)`

• Description: Returns a finite domain item `Var` from a list of fd items `ListOfVars` and the rest of the list `RestOfVars`in a deterministic way. Currently it always returns the first item of the list.
• The following properties should hold at call time: `+ListOfVars` is a list of `fd_item`s. (`basic_props:list/2`) `-Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-RestOfVars` is a list of `fd_item`s. (`basic_props:list/2`)

PREDICATE: choose_free_var/2:

Usage: `choose_free_var(+ListOfVars, -Var)`

• Description: Returns a free variable `Var` from a list of fd items `ListOfVars`. Currently it always returns the first free variable of the list.
• The following properties should hold at call time: `+ListOfVars` is a list of `fd_item`s. (`basic_props:list/2`) `-Var` is a free variable. (`term_typing:var/1`)

PREDICATE: choose_var_nd/2:

Usage: `choose_var_nd(+ListOfVars, -Var)`

• Description: Returns non deterministically an fd item `Var` from a list of fd items `ListOfVars` .
• The following properties should hold at call time: `+ListOfVars` is a list of `fd_item`s. (`basic_props:list/2`) `-Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`)

PREDICATE: choose_value/2:

Usage: `choose_value(+Var, -Value)`

• Description: Produces an integer value `Value` from the domain of `Var`. On backtracking returns all possible values for `Var`.
• The following properties should hold at call time: `+Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-Value` is an integer. (`basic_props:int/1`)

PREDICATE: retrieve_range/2:

Usage: `retrieve_range(+Var, -Range)`

• Description: Returns in `Range` the range of an fd item `Var`.
• The following properties should hold at call time: `+Var` is a free variable. (`term_typing:var/1`) `-Range` is the range of a finite domain entity. (`user(... /fd_doc):fd_range/1`)

PREDICATE: retrieve_store/2:

Usage: `retrieve_store(+Var, -Store)`

• Description: Returns in `Store` a representation of the constraint store of an fd item `Var`.
• The following properties should hold at call time: `+Var` is a free variable. (`term_typing:var/1`) `-Store` is a representation of the constraint store of a finite domain entity. (`user(... /fd_doc):fd_store/1`)

PREDICATE: glb/2:

Usage: `glb(+Var, -LowerBound)`

• Description: Returns in `LowerBound` the lower bound of the range of `Var`.
• The following properties should hold at call time: `+Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-LowerBound` is an integer. (`basic_props:int/1`)

PREDICATE: lub/2:

Usage: `lub(+Var, -UpperBound)`

• Description: Returns in `UpperBound` the upper bound of the range of `Var`.
• The following properties should hold at call time: `+Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-UpperBound` is an integer. (`basic_props:int/1`)

PREDICATE: bounds/3:

Usage: `bounds(+Var, -LowerBound, -UpperBound)`

• Description: Returns in `LowerBound` and `UpperBound` the lower and upper bounds of the range of `Var`.
• The following properties should hold at call time: `+Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-LowerBound` is an integer. (`basic_props:int/1`) `-UpperBound` is an integer. (`basic_props:int/1`)

PREDICATE: retrieve_list_of_values/2:

Usage: `retrieve_list_of_values(+Var, -ListOfValues)`

• Description: Returns in `ListOfValues` an enumeration of al the values in the range of `Var`
• The following properties should hold at call time: `+Var` is a finite domain entity, i.e. either a finite domains variable or an integer. (`user(... /fd_doc):fd_item/1`) `-ListOfValues` is a list of `int`s. (`basic_props:list/2`)