Non-crossing knight tours


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.


LONGEST KNOWN OPEN TOURS
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

LONGEST KNOWN CLOSED TOURS
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