# Knight's tour

## Introduction

The knight's tour is a mathematical problem concerning a knight on a chessboard.

The knight shall be moved on the longest possible path according to the moves allowable in chess.

## Model

# Knight's tour # # Determine a closed path a knight can travel # on a chess board covering all fields. # size of field param m; param n; # coluns set X := 1..m; # rows set Y := 1..n; # fields set F := X cross Y; # moves set M := setof{ (x1,y1) in F, (x2,y2) in F : (abs(x1-x2)==2 && abs(y1-y2)==1) || (abs(x1-x2)==1 && abs(y1-y2)==2)} (x1,y1,x2,y2); # transported remaining path length var v{(x1,y1,x2,y2) in M} >= 0; # move is chosen var w{(x1,y1,x2,y2) in M}, binary; # position of field in tour var p{(x,y) in F}; # start of the tour s.t. start : p[1,1]=m*n; # number of incoming moves s.t. win{(x2,y2) in F} : sum{(x1,y1,x2,y2) in M} w[x1,y1,x2,y2] = 1; # number of outgoing moves s.t. wout{(x1,y1) in F} : sum{(x1,y1,x2,y2) in M} w[x1,y1,x2,y2] = 1; # transported remaining path length s.t. vout{(x1,y1) in F} : sum{(x1,y1,x2,y2) in M} v[x1,y1,x2,y2] = p[x1,y1]; # remaining path length s.t. vin{(x2,y2) in F} : sum{(x1,y1,x2,y2) in M} v[x1,y1,x2,y2] = 1 + p[x2,y2] - if (x2==1 && y2==1) then m * n else 0; # remaining path length can only be transported if move is chosen s.t. vmax{(x1,y1,x2,y2) in M} : v[x1,y1,x2,y2] <= m*n*w[x1,y1,x2,y2]; solve; # output the result # output printf "+"; for { x in X } { printf "---+"; } printf "\n"; for {y in Y} { printf "|"; for { x in X } { printf "%3d|", m*n+1-p[x,y]; } printf "\n"; printf "+"; for { x in X } { printf "---+"; } printf "\n"; } data; # size of field # A closed tour is not possible for m <= n if # m and n are both odd, or # m = 1, 2, or 4, or # m = 3 and n = 4, 6, or 8. param m:= 8; param n:= 8; end;