Knight's Tour

The problem can be restricted by demanding the tour to be closed (or reentrant): from the last square in the tour the knight should be able to reach the starting square.

One might think that the problem ought to be solved nowadays when we have got computers. An easy way of solving it seems to be to let the computer test all possible ways of choosing ways the knight has. Most choices will result in a dead end situation - the knight gets to a square from which it cannot get away without getting to a square already visited. In that situation just back one step, and choose another square to go to. And if one already have tried all possible choices from that square, just back another step. Backtracking is the name of that strategy, and it is often applicable

On a normal 8 * 8 squares board the problem shows to be surprisingly big. Actually so big that simple counting of tours is out of reach even for the fast computers of today. The problem has to be tackled in other ways.

1995 Martin Löbbing and Ingo Wegener wrote a paper with the appealing title: "The Number of Knight's Tours equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams". They obtained their result by running 20 Sun stations for four months (idle time, efficient CPU time being less).
Brendan McKay issued a comment 18 Feb 1997. He used another method (split the board into two halves) and got the result 13,267,364,410,532.   [4]

To give an idea of the magnitude of these numbers, consider a computer searching and finding tours at a speed of 1 million tours per minute (266 MHz PC). This may seem pretty fast, but the computer will nevertheless have to run for more than 9,213 days and nights - i.e. for more than 25 years - to reach the number of tours given by Brendan McKay.

• The Java applet on this side uses search with backtracking, strengthened with a couple of algorithms that early will stop search paths resulting in dead ends . (Without them a pure backtracking strategy would require 3 430 271 572 moves up to the first complete tour - which would be kind of boring. Now 94 moves will suffice.) Click on the board with mouse left to search move by move. Use mouse right to get full complete tours at once.

Actually there is no need for backtracking to achieve a completed knight's tour. There is an old efficient method that goes straight to that goal. It is described and demonstrated at the next page about Warnsdorff's rule.

2. Mark R. Keen gives more details about the interesting history of the problem and some graph theory in his beautiful paper: "THE KNIGHT'S TOUR"

3. George Peter Jelliss has made a comprehensive history/bibliography of the problem in his Knight's Tour Notes.(Starting at 2200 B.C. !)

4. These papers can be found in the Electronic Journal of Combinatorics,Volume 3,(no 1)
Both papers in postscript format; directly readable on that address are an "Abstract" and "Comments".
(Martin Löbbing and Ingo Wegener have later re-run their computations which were faulty - see their "Comments" above - and confirmed the result of Brendan McKay. The joint paper about this still remains to be written. [private correspondence with Brendan McKay] )

5. In Japan it's done with the help of neural networks ! Here's an applet:
Takayuki Saito has made Neural Network Demonstration for Knight's Tour Problems
Highly fascinating, although it has a tendency to produce several independent tours on the same board, rather than one continuos tour. Maybe a consequence of the technique used.