generic_nary_constraint

Purpose

This constraint can be used to propagate a user-defined constraint over n variables (its propagation is based on the GAC2001 algorithm (cf. [Bes01]).

Synopsis

function generic_nary_constraint(vars:arrray of cpvar, fctname:string, userparam:integer) : cpctr

function generic_nary_constraint(vars:cpvarlist, fctname:string, userparam:integer) : cpctr

function generic_nary_constraint(vars:arrray of cpvar, fctname:string, propagation: integer, userparam:integer) : cpctr

function generic_nary_constraint(vars:cpvarlist, fctname:string, propagation: integer, userparam:integer) : cpctr

function generic_nary_constraint(vars:set of cpvar, fctname:string, userparam:integer) : cpctr

function generic_nary_constraint(vars:set of cpvar, fctname:string, propagation: integer, userparam:integer) : cpctr

Arguments

vars	a set, array, or cpvarlist of decision variables
fctname	name of the function specifying the user-defined constraint, such a function necessarily takes a cpvarlist/cptuple and an integer (the value of userparam) as arguments and returns a Boolean.
userparam	a user parameter
propagation	the level of propagation to achieve. 0 stands for GAC algorithm, 1 for AC algorithm and 2 for Forward-Checking algorithm

Return value

An n-ary constraint over a set of variables

Example

The following example shows how to use the generic_nary_constraint constraint to solve the classical Euler Knight Tour problem:

model "Euler Knight Moves"
 uses "kalis"

 parameters
  S = 8                                  ! No. of rows/columns
 end-parameters

 N:= S * S                               ! Total number of cells
 setparam("KALIS_DEFAULT_LB", 0)
 setparam("KALIS_DEFAULT_UB", N-1)

 forward public function valid_knight_move(vals: cptuple, s: integer): boolean

 declarations
  PATH = 1..N                            ! Cells on the board
  pos: array(PATH) of cpvar              ! Position p in tour
  propagation : integer                  ! Alg choice: 0, 1, or 2
 end-declarations

! Selecting the propagation algorithm for the generic nary constraint
 propagation := 0

! Setting names of decision variables
 forall(i in PATH) setname(pos(i), "Position"+i)

! Fix the start position
 pos(1) = 0

! Each cell is visited once
 all_different(pos, KALIS_GEN_ARC_CONSISTENCY)

! The knight's path obeys the chess rules for valid knight moves
 forall(i in 1..N-1)
  generic_nary_constraint({pos(i), pos(i+1)}, "valid_knight_move",propagation,S)
 generic_nary_constraint({pos(N), pos(1)}, "valid_knight_move",propagation,S)

! Setting enumeration parameters
 cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN,
                  KALIS_MAX_TO_MIN, pos, 14))

! Search for up to NBSOL solutions
 solct:= 0
 if not cp_find_next_sol then
  writeln("No solution")
 else
  writeln(pos)
 end-if

! **** Test whether the move from a to b is admissible ****
 public function valid_knight_move(vals: cptuple, s: integer): boolean
  declarations
   xa,ya,xb,yb,delta_x,delta_y: integer
   a,b : integer
  end-declarations
  ! Current position data
  a := getelt(vals,1)  ! 1 : pos(i)
  b := getelt(vals,2)  ! 2 : pos(i+1)

  xa := a div s
  ya := a mod s
  xb := b div s
  yb := b mod s
  delta_x := abs(xa-xb)
  delta_y := abs(ya-yb)
  returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
 end-function

end-model

Contents

Index

Glossary

Search Results

generic_nary_constraint

generic_nary_constraint