In the Journal of Recreational Mathematic of July 1968, L. D. Yarbrough introduced
a new variant on the classic problem of knight's tour. In addition to the rule
that a knight touring a chessboard cannot visit the same cell twice (except
for the final jump that can reach the first square, in this case, the tour is
called **closed** otherwise it's **open**), the knight
is also not permitted to cross its own path (the path consists of straight lines
drawn between the starting and ending square of every jump).

This variant has several names: "non-crossing knight's tour" or "uncrossed
knight's tour".

In his "Mathematical Circus", Martin Gardner presents this problem
and explains that the 6x6 tour found by Yarbrough can be improved from 16 to
17 jumps, you can try to play with this link.
Donald Knuth
wrote a program to explore all boards upto 8*8. The solutions are 2,5,10,17,24
and 35 (this is sequence A003192
from Online Encyclopedia of Integer Sequences)

Strangely, this problem did not receive much consideration, although it's **much
harder** to solve than the normal knight tour problem ! For example:
the knight tour problem can be solved via the Warnsdorf heuristic or a recent
divide-and-conquer algorithm among other methods, and we still don't know any
heuristic on the uncrossing variant.

This problem has been posed in the 2002 ACM programming contest:

http://www.lab2.kuis.kyoto-u.ac.jp/~yanagis/acmicpc/past/02AsiaManila/2002Manila.pdf

Here are some links for more informations:

http://mathworld.wolfram.com/KnightsTour.html

http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/twixt.np

In August 2000, Eric Bainville wrote a program to solve all open and closed
tours on boards from 4*4 to 8*8. He also computed the longest closed tours on
9*9. You can find these tours on this page.

Recently, Y. M. Ojisan found an open 43 tour on the 9*9 board. You can see his
solution (along with a 6*6 Java elegant solver) there:

http://web2.incl.ne.jp/yaoki/aweek137.htm

http://web2.incl.ne.jp/yaoki/week137.htm

On rectangular boards, Ciara Caltagirone solved the problem on boards 2*m, 3*m,
4*m and 5*m:

http://www.stetson.edu/departments/mathcs/students/research/presentations/math/ciara.ppt

What about larger boards ?

In 1973, Robin Merson found a 74 tour on a 11*11 board, and also a 75 tour on
a 10*12:

http://www.mathpuzzle.com/leapers.htm

In Jeux&Stratégie number 18, Pierre
Berloquin published an impressive 235 tour on a 18*18 found by M. Cornuejols.

George P. Jelliss recently compiled the best
results. Most of them come from Robin Merson's work.

m\n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

3 | 2 | |||||||||||||

4 | 4 | 5 | ||||||||||||

5 | 5 | 7 | 10 | |||||||||||

6 | 6 | 9 | 14 | 17 | ||||||||||

7 | 8 | 11 | 16 | 21 | 24 | |||||||||

8 | 9 | 13 | 19 | 25 | 30 | 35 | ||||||||

9 | 10 | 15 | 22 | 29 | 35 | 42 | 47 | |||||||

10 | 11 | 17 | 25 | 32 | 39 | 47 | ? | 61 | ||||||

11 | 12 | 19 | 28 | 35 | 44 | ? | ? | ? | 76 | |||||

12 | 13 | 21 | 31 | 39 | 49 | ? | ? | 75 | ? | 94 | ||||

13 | 14 | 23 | 34 | 43 | ? | ? | ? | ? | ? | ? | 113 | |||

14 | 15 | 25 | 37 | 42 | ? | ? | ? | ? | ? | ? | ? | 134 | ||

15 | 16 | 27 | 40 | ? | ? | ? | ? | ? | ? | ? | ? | ? | 158 | |

16 | 17 | 29 | 43 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | 181 |

m\n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

3 | 0 | |||||||||||||

4 | ? | 4 | ||||||||||||

5 | ? | 4 | 8 | |||||||||||

6 | 6 | 8 | 12 | 12 | ||||||||||

7 | ? | 10 | 14 | 18 | 24 | |||||||||

8 | ? | 10 | 18 | 22 | 26 | 32 | ||||||||

9 | ? | 12 | 20 | 24 | 32 | 36 | 42 | |||||||

10 | ? | ? | 22 | 28 | 36 | ? | ? | 54 | ||||||

11 | ? | ? | 24 | 32 | 38 | ? | ? | ? | 70 | |||||

12 | ? | ? | 28 | 36 | ? | ? | ? | ? | ? | 86 | ||||

13 | ? | ? | 30 | ? | ? | ? | ? | ? | ? | ? | 104 | |||

14 | ? | ? | 34 | ? | ? | ? | ? | ? | ? | ? | ? | 124 | ||

15 | ? | ? | 38 | ? | ? | ? | ? | ? | ? | ? | ? | ? | 148 | |

16 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | 172 |

Go to the index page