this project is to enumerate all closed knight's tours on a 8x8 chessboard.
This has been done in 1996 by Loebbing/Wegener and McKay.
First they had different numbers, but finally agreed that there
are 13_267364_410532 of them.
(in German) for a description of their used algorithms
They used a complicated method with dividing the board into two
We want to check the number with a different method.
We use a straightforward approach, using
a simple hamilton-cycles program which works
(with small modifications) for any graph.
So the method can also be used to compute open knight-tours,
We also want to collect some more information about the search-tree.
While it's inpracticable to store all the knight tours
(there are too many !) we want to use this information to
make a program which reads an arbitrary knight tour as input
and -after some minutes- prints the number of this tour
in our imaginary (but not stored) list of all knight tours.
The 8*8 knight-graph is split into 24^4 subgraphs by taking all
possibilities for subchains of length 5 with the 4 edges
being the middle vertices in these 4 subchains.
These 331776 subproblems are sorted by their isomorphism-classes
and we get 41790 isomorphism classes ,
41170 of multiplicity 8, 590 of multiplicity 4 ,
26 of multiplicity 2 and 4 of multiplicity 1.
To get an estimate of the running time,
99 of these subproblems were taken at random and ran
for 84 hours in total (max=2.5h,min=1m) finding 4.6e9 tours
(max=3.4e8,min=2.5e3) on a K6-2-500 with my old program,
which is 3 times slower (270 cycles/node) than JC's program,
so this gives an estimate of about 80 days and 1.9e12 tours
(correct value:1.6e12) on a 3GHz computer to do the whole
If you want to participate in the computation
you can pick a range of about 400 of these 41790 graphs, which you
check for Hamilton cycles using the program
The program will return the complete node-counts for each subproblem.
Also maybe some statistics of the solutions, see below.
The solution-numbers will be collected, multiplied by the
multiplicity of their isomorphism class and added together.
This will hopefully yield 13_267364_410532...
once the first reports come in, the solver-statistics will be
displayed here and the not yet computed subproblems to avoid
We are still reflecting, which properties of all the solutions
should be checked and stored... (send suggestions to email@example.com)
In theory we can make a statistics of :
- the numbers of crossing-edges of the knight tours
- branching factors , product of the numbers of possible choices
at each step in a solution
- direction statistics of the moves : how often an angle of
2*pi-2*atn(.5) is taken during the tour
- how many short edges are in the tour
(move(i) and move(i+3) are a knight's move apart)
- how many "quartes" of type "diamond", "square" or "Beverley"
there are (see:http://www.ktn.freeuk.com/mg.htm#(3))
- number of unit squares, centered at a grid-point not crossed by one
of the 64 edges of the tour
- examine the graph which results when the 64 edges of the hamilton cycle
are removed : number of holes,cycles,colorings,etc.
There can't be another knight's tour in it since the edges are only of
degree 2. But maybe there is a knight's tour and a nightrider's
tour on different edges in the 8*8 nightrider's graph ?
we will spend about 10000 CPU cycles in average per tour,
and 100 cycles in average per knight's placement , so there
should be some time for additional tests without blowing up the
See the program
for a version which computes and stores data about the number of
knight-tours with 14 special properties.
It takes about 10 times longer than kn8x8f and stores more data.