The problem of finding knight's tours on a chessboard is well documented in the literature of Recreational Mathematics and is also known in ORMS circles as an instance of the Traveling Salesperson Problem (TSP). A similar but much lesser known puzzle taken from the whimsical world of Fairy Chess is that of identifying fiveleaper tours. A knight move may be described as having coordinates {1,2} meaning in a single move it travels one square in a particular direction and two squares in an orthogonal direction. Using this notation the legal moves for a fiveleaper have coordinates {0,5} or {3,4}. In either event the Euclidean distance traveled is five squares.

A brief introduction to fiveleapers is at Math Puzzle and further background together with an impressive array of results is at Fiveleaper Tours.

A tour requires that the fiveleaper visits every square on a board once and once only using legal moves. The fiveleaper tours come in two varieties, that is, open and closed tours. In an open tour there is no restriction on where the tour begins and ends. In a closed tour the start and finish squares must be separated by a legal move and the fiveleaper could close the tour by making this final move.

We begin the formulation for a closed tour by defining s as the number of squares per side of a square board and n=s² as the number of squares on the board. Also
N = 1, ..., n.

A_ij = 1 if square i to square j is a legal move, 0 otherwise

An Xpress-Mosel code fragment to generate this table of legal moves is here.

Decision variables required are

x_ij = 1 if move from square i to square j forms part of tour, 0 otherwise

z_i variables for sub-tour breaking constraints

The objective is merely to fulfil the conditions of the tour so any arbitrary objective function may be chosen. It is useful to select a simple expression in order to avoid unnecessay computations. The complete formulation for the closed tour is as follows.

Mosel code to implement the closed tour model is here.

The open tour requires identical variable definitions and a couple of modifications to the above giving the following model:

Mosel code to implement the open tour model is here.

An interesting property of the 8x8 board is that a fiveleaper on any square has exactly four legal moves available. This was first noted by G.P.Jellis who realised that, as a consequence, any closed tour would involve two unused moves at every square and wondered whether a second closed tour could be identified linking these unused moves. The question was answered by Tom Marlow in 1991 and his solution is presented at Math Puzzle. The closed tour formulation may be easily modified to identify such a dual tour by defining variables y_ij and w_i for the second tour which are equivalent to x_ij and z_i. The precedence and subtour-breaking constraints for the second tour are added to the model and the constraints ensuring only legal moves are replaced by

Mosel code to implement the dual tour model is here.

Larger board sizes, rectangular boards

The model implementations referred to above for a standard chessboard (s=8) can be solved within seconds or at most a few minutes on a PC. There are no solutions to the fiveleaper tour problem for smaller boards, but we may well try to solve it for larger ones. Unfortunately, with increasing board sizes, the models described above quickly grow too large to be solvable within a reasonable amount of time (see the table with an overview of solution times below). However, it is possible to reformulate these models reducing them to a more managable size by

1. removing unnecessary variables
2. initially stating only a subset of the constraints and adding iteratively those that are violated of the remaining ones until a solution is found

We shall first take a look at the variables: on an 8x8 board there are four permissible moves per square but for every square i we have defined variables x_ij for moving to all 64 squares of the board, that means, 16 times more than we need. Most of these variables get immediately fixed to 0 by the value of A_ij. We now only define those variables that represent permissible moves as shown in this Mosel code fragment. This formulation also has the advantage that much less terms are summed up in the predecessor and successor constraints. A visualisation of the spasity pattern of the permissible moves matrix is below (Mosel code to produce this graphical output).

We now state the model as follows:

	minimise sum(i,j in N  | move i->j is permissible ) x_{i,j} 

	Each square precedes one other
	 forall(i in N): sum(j in N  | move i->j is permissible ) x_{i,j} = 1

	Each cell is preceded by one other
	 forall(j in N): sum(i in N | move i->j is permissible ) x_{i,j} = 1

	forall(i,j in N | move i->j is permissible ): x_{i,j} in {0,1}
				

The objective function in this model is the sum of all variables (x₁₁ is not a permissible move and hence not defined). Another possibility would be to use simply the value 0.
We do not need the bounds given by A_ij any more but we have also left out all constraints (and the variables z_i) that are required to exclude subtours. Instead we implement the following subtour breaking algorithm:

• solve the problem
• if problem is feasible:
• call procedure 'break_subtour':
• construct the tour starting at square 1
• if this tour is not the complete tour:
• add a subtour breaking constraint for this subtour
• add all squares of this tour to the set of visited squares
• for all squares not yet visited:
• construct the subtour starting at this square
• add a subtour breaking constraint for this subtour
• add all squares of this tour to the set of visited squares
• re-solve the problem
• iteratively call again procedure 'break_subtour'
• else: a solution is found

A subtour breaking constraint for a tour T is of the following form:

sum(i,j in N | move i->j in T) x_{i,j} <= size(T) - 1

where size(T) denotes the number of squares forming the tour T.

The complete Mosel code of this algorithm can be found here.

We have thus reduced the initial model from roughly 2n^2+2n constraints to only 2n constraints. For a 8x8 board this means a reduction from over 8000 to 128 constraints; for a 14x14 board this reduces the number of constraints from more than 75,000 to just 392. The resulting problem, even after the subtour breaking algorithm has added a few hundred constraints, is solvable considerably faster than the original one. This leads especially for larger instances to much shorter total solution times than with the initial models. The following table gives an overview of the solution times. (All times are measured on a PC Pentium4, 1.5GHz, 512Mb under Linux with Xpress-MP Release 2003C.)

Another extension of the original problem on a 8x8 chess board is to consider rectangular boards. The smallest possible area size is a 6x9 rectangle. The previous models can easily be modified to accomodate rectangular boards (see the Mosel code here): only the calculation of the permissible moves and the solution output require some changes.

Examples of graphical solution output produced by Xpress-IVE (Mosel code to produce this graphical output):

References

Guéret, C., Prins, C., Sevaux, M., Translated and Revised by Susanne Heipcke (2002), Applications of Optimization with Xpress-MP, Dash Optimization,

Marlow, T.W. and Jelliss G.P. (2002), Knight's Tour Notes - Note 9f,

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To reference this paper, please use:  Chlond, M.J., R.C. Daniel, and S. Heipcke (2003), "Fiveleapers a-leaping," INFORMS Transactions on Education, Vol. 4, No 1,  http://ite.pubs.informs.org/Vol4No1/ChlondDanielHeipcke/