 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Euler knight tour problem

Description
Euler knight tour problem:
• 'all-different' and generic binary constraints; branching strategy for variables (eulerkn.mos).
• Alternative implementation using subtour elimination constraints with 'implies' (eulerkn2.mos).
• Third model formulation using a 'cycle' constraint in its simplest form (eulerkn3.mos) or with successor and predecessor variables (eulerkn3b.mos).
Further explanation of this example: 'Xpress Kalis Mosel User Guide', Section 3.11 Generic binary constraints: Euler knight tour

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

eulerkn3.mos

(!****************************************************************
CP example problems
===================

file eulerkn3.mos

Euler knight problem.
Finding a tour on a chess-board for a knight figure,
such that the knight moves through every cell exactly
once and returns to its origin.
- Alternative implementation using a 'cycle' constraint -

*** This model cannot be run with a Community Licence
for the default data instance ***

(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2007, rev. Mar. 2013
*****************************************************************!)

model "Euler Knight Moves"
uses "kalis"

parameters
S = 8                                   ! Number of rows/columns
NBSOL = 1                               ! Number of solutions sought
end-parameters

forward procedure calculate_successors(p: integer)
forward procedure print_solution(sol: integer)

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

declarations
PATH = 0..N-1                           ! Cells on the chessboard
succ: array(PATH) of cpvar              ! Successor of cell p
end-declarations

! Calculate set of possible successors
forall(p in PATH) calculate_successors(p)

! Each cell is visited once, no subtours
cycle(succ)

! Search for up to NBSOL solutions
solct:= 0
while (solct<NBSOL and cp_find_next_sol) do
solct+=1
cp_show_stats
print_solution(solct)
end-do

! **** Calculate possible successors ****
procedure calculate_successors(p: integer)
declarations
SuccSet: set of integer                ! Set of successors
end-declarations

xp := p div S
yp := p mod S

forall(q in PATH) do
xq := q div S
yq := q mod S
delta_x := abs(xp-xq)
delta_y := abs(yp-yq)
if (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3) then
SuccSet +={q}
end-if
end-do

setdomain(succ(p), SuccSet)
end-procedure

!****************************************************************
! **** Solution printing ****
procedure print_solution(sol: integer)
writeln("Solution ", sol, ":")
thispos:=0
nextpos:=getval(succ(0))
ct:=1
while (nextpos<>0) do
write(thispos, if(ct mod 10 = 0, "\n ", ""), " -> ")
val:=getval(succ(thispos))
thispos:=nextpos
nextpos:=getval(succ(thispos))
ct+=1
end-do
writeln("0")
end-procedure

end-model

`   