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. -------------------------------------------- [update 2019 : how could I have written that in 2005, which now even I myself don't understand ? Here a hopefully better explanation : A closed 8x8 closed knight's tour contains 24 possible different subchains of length 5 around each corner with the corner in the middle of that subchain. e.g. {a3,b4,d4,e3,e1}-c2-a1-b3-{a5,c5,d4,d2,c1} with d4-c2-a1-b3-d4 excluded For each corner there are in total 12 possible squares=vertices in those subchains and they are distinct for different corners. We start with any such possible 4-subset of corner-5-subchains and try to complete them into a knight's tour. That gives 24^4 possibilities from 41790 symmetry classes. Here is a file with the first tour from each class: http://magictour.free.fr/41790.7z ] --------------------------------------------- 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. =============update 2019============================================= I did that calculation from 2019/07/23 to 2019/08/08 in 16 days on 8-12 threads of a Ryzen 1700x . I got 1692674826245 closed knight's tours on the 8x8 altogether in the 41790 ranges. See the full node-counts in the file here : http://magictour.free.fr/SOLURYZN For convenience of notation we require a closed knight's tour to start with "a1-c2-..." and end with "-b3". This prevents counting reversed tours and sets the start to the bottom left corner with the squares numbered as usual in chess. "Minimal" tours are alphabetically minimal in their symmetry-class with respect to this notation. 620 out of the 41790 ranges are symmetric with 62345824424 tours in them, 590 of 2-fold symmetry with 52900283834 tours, 26 of 4-fold symmetry with 3685727738 tours and 4 of 8-fold symmetry with 5759813952 tours ; the remaining 41170 ranges had 163032900721 tours. The only symmetry in full 8x8 closed knight's tours is 180-rotation and there are 608233 symmetry classes of these with 2432932 tours. In the symmetric ranges there are 2,4,8 tours which belong to the same symmetry-class (except possibly when the tour itself is symmetric). So, to get the total number of symmetry-classes from the 41790-calculation we have for each range to divide by the size of the range-symmetry-class. Then we must add back half of the symmetric tours, since members of that symmetry-class occurred only half as often as the nonsymmetric ones. The calculated numbers with these corrections for the 41790 ranges are listed in this file : http://magictour.free.fr/41790.8x8 And it matches the previously reported count of 1658420855433 symmetry classes achieved in 1997 with another, faster method that enumerated the tours by grouping them but without creating them all. https://users.cecs.anu.edu.au/~bdm/papers/knights.pdf ---------------------------------------------------------- Now, it _is_ feasable to store all the 1658420855433 symmetry classes in compressed format on a 4TB harddrive. Then they can be uncompressed, range by range, and checked for some property or such. ---------------------------------------------------------------