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)
• Documentation on exports (fd)

Usage and interface (fd)

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_items. (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 RestOfVarsin 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_items. (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_items. (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_items. (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_items. (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 ints. (basic_props:list/2)

Go to the first, previous, next, last section, table of contents.