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.

eulerkn.mos

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

file eulerkn.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.

Model formulation for 8x8 chessboard:
We number the cells of the chessboard from 0 to 63 (64 cells)

A  B  C  D  E  F  G  H
+--+--+--+--+--+--+--+--+
8 |0 |1 |2 |3 |4 |5 |6 |7 |
+--+--+--+--+--+--+--+--+
7 |8 |9 |10|11|12|13|14|15|
+--+--+--+--+--+--+--+--+
6 |16|17|18|19|20|21|22|23|
+--+--+--+--+--+--+--+--+
5 |24|25|26|27|28|29|30|31|
+--+--+--+--+--+--+--+--+
4 |32|33|34|35|36|37|38|39|
+--+--+--+--+--+--+--+--+
3 |40|41|42|43|44|45|46|47|
+--+--+--+--+--+--+--+--+
2 |48|49|50|51|52|53|54|55|
+--+--+--+--+--+--+--+--+
1 |56|57|58|59|60|61|62|63|
+--+--+--+--+--+--+--+--+

The path that the knight will follow is represented by 64 variables "pos"
that can take values from 0 to 63.
For example, pos[12] = 45 means that the 12th cell visited by the knight
is the cell F:3

Constraint 1: each cell is visited only once.
---------------------------------------------
We simply post an all_different constraint on all the path variables

Constraint 2: the path of the knight must follow the chess rules.
-----------------------------------------------------------------

The knight (Kn) can move to the crossed cells (xx):

+--+--+--+--+--+
|  |xx|  |xx|  |
+--+--+--+--+--+
|xx|  |  |  |xx|
+--+--+--+--+--+
|  |  |Kn|  |  |
+--+--+--+--+--+
|xx|  |  |  |xx|
+--+--+--+--+--+
|  |xx|  |xx|  |
+--+--+--+--+--+

If the knight is in the cell numbered c, it is authorized to move to the
following cells:
c + 1 - 16  [One cell right, two cells up  ]
c - 1 - 16  [One cell left, two cells up   ]
c + 1 + 16  [One cell right, two cells down]
c - 1 + 16  [One cell left, two cells down ]
c + 2 - 8   [Two cells right, one cell up  ]
c - 2 - 8   [Two cells left, one cell up   ]
c + 2 + 8   [Two cells right, one cell down]
c - 2 + 8   [Two cells left, one cell down ]

This constraint is represented by a generalized binary constraint,
the function valid_knight_move defined in the model provides the
evaluation for pairs of values.

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

(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Sep 2018
*****************************************************************!)

model "Euler Knight Moves"
uses "kalis"

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

forward procedure print_solution(sol: integer)
forward public function valid_knight_move(a:integer, b:integer): boolean

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

declarations
PATH = 1..N                            ! Cells on the chessboard
pos: array(PATH) of cpvar              ! Cell at position p in the tour
end-declarations

! Fix the start position
pos(1) = 0

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

! The path of the knight obeys the chess rules for valid knight moves
forall(i in 1..N-1)
generic_binary_constraint(pos(i), pos(i+1), "valid_knight_move")
generic_binary_constraint(pos(N), pos(1), "valid_knight_move")

! 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
while (solct<NBSOL and cp_find_next_sol) do
solct+=1
cp_show_stats
print_solution(solct)
end-do

! **** Test whether the move from position a to b is admissible ****
public function valid_knight_move(a:integer, b:integer): boolean
declarations
xa,ya,xb,yb,delta_x,delta_y: integer
end-declarations

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

!****************************************************************
! Solution printing
procedure print_solution(sol: integer)
writeln("Solution ", sol, ":")
forall(i in PATH)
write(getval(pos(i)), if(i mod 10 = 0, "\n ", ""), " -> ")
writeln("0")
end-procedure

end-model