[ The ECLiPSe Libraries | Reference Manual | Alphabetic Index ]

library(tentative_constraints)

Tentative value implementations for some basic constraints

Predicates

alldifferent_t(+Cs, +MC)
Tentative value implementation of alldifferent constraint
alldifferent_t(+Xs, +Cs, +MC)
Tentative value implementation of alldifferent/2 constraint
eq_t(?X, ?Y, +MC)
Tentative value implementation of $=/2 arithmetic equality constraint
integral_t(?X, ?Epsilon, +MC)
Tentative value implementation of approximate integrality
neq_t(?X, ?Y, +MC)
Tentative value implementation of $\=/2 arithmetic disequality constraint

Reexports

reexport tentative

Other Exports

export op(700, xfx, $=)
export op(700, xfx, $\=)

Description

This library contains tentative value implementations for some basic constraints. It is intended to be used together with lib(tentative), which provides the underlying primitives and facilities to create tentative variables, manage constraint sets, and to do search.

Examples

    %
    % The following code implements a solution to the N-queens problem,
    % using a steepest-ascent hill-climbing heuristic.
    %

    :- lib(tentative).
    :- lib(tentative_constraints).

    queens(N, Board) :-
	    dim(Board, [N]),			% make variables
	    tent_set_random(Board, 1..N),	% init tentative values

	    dim(Pos, [N]),			% aux arrays of constants
	    ( foreacharg(I,Pos), for(I,0,N-1) do true ),
	    dim(Neg, [N]),
	    ( foreacharg(I,Neg), for(I,0,-N+1,-1) do true ),

	    CS :~ alldifferent(Board),		% setup constraints ...
	    CS :~ alldifferent(Board, Pos),	% ... in conflict set CS
	    CS :~ alldifferent(Board, Neg),

	    cs_violations(CS, TotalViolation),	% search part
	    steepest(Board, N, TotalViolation),

	    tent_fix(Board),			% instantiate variables
	    cs_clear_satisfied(CS).		% clean up conflict set


    steepest(Board, N, Violations) :-
	    vs_create(Board, Vars),		% create variable set
	    Violations tent_get V0,		% initial violations
	    SampleSize is fix(sqrt(N)),		% neighbourhood size
	    (
		fromto(V0,_V1,V2,0),		% until no violations left
		param(Vars,N,SampleSize,Violations)
	    do
		vs_worst(Vars, X),		% get a most violated variable
		tent_minimize_random(		% find a best neighbour
		    (				% nondeterministic move
			random_sample(1..N,SampleSize,I),
			X tent_set I
		    ),
		    Violations,			% violation variable
		    I				% best move-id
		),
		X tent_set I,			% do the move
		Violations tent_get V2		% new violations
	    ).

About

See Also

library(tentative)
Generated from tentative_constraints.eci on Mon Mar 31 03:15:23 2008