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. See : McKay-paper
Lee-paper
(in German) for a description of their used algorithms They used a complicated method with dividing the board into two halftours. 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, leaper-tours etc. 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 computation . 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 kn8x8f.exe
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 double-computations. We are still reflecting, which properties of all the solutions should be checked and stored... (send suggestions to sterten@aol.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 pi/2-2*atn(.5),pi/2,pi-2*atn(.5),pi,3*pi/2-2*atn(.5),3*pi/2, 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 search significantly. See the program kn8x8.exe
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.