how to enumerate knight's tours
--------------------------------
the methods below also work for general Hamilton Paths in (undirected)
graphs G=(V,E) but the efficency is different. Methods (3) and (4) are only
good, when there is a subset S of V with few edges from S to V-S ,
S and V-S should have almost the same size.
(1) brute force method : backtrack through all paths in the knight's graph
this produces about one 8*8 knight's tour per second with 1 GHz
(2) same as (1) but avoid leaving nonvisited vertices with less than
two unvisited neighbors. They cannot be included in a Hamilton
Path, -unless they are the endpoints.
This produces about 100000 8*8 knight's tours per second with 1 GHz.
(3) cover subregions with knigh-paths.
For a subset S of V consider the induced subgraph of a
Hamilton path (n vertices,n-1 edges) on S. (intersection with SxS)
It is the disjoint union of k paths on S with both endpoints
having a neighbor in V-S and the vertex in paths of length one
has 2 neighbors in V-S.
Call any graph with this property a "partial S-tour".
The collection (set,superset) of the sets of endpoints
of a partial S-tour is the "pathstructure" of the partial S-tour.
The number of Hamilton cycles whose intersection with S
is a given partial S-tour depends only on the pathstructure
of the partial tour, i.e. partial tours with the same
pathstructure can be extended to Hamilton cycles in the
same number of ways.
For knight's graphs on a*b rectangles we enumerate the cells
from left to right, top to bottom as you read normal text like this.
For better efficency we rotate the rectangle so that the height
is larger or equal than the width.
This gives vertexset V={1,..,n} with n=a*b.
Now, choose S={1,..,s} at step S and compute S-pathstructures
and counts of S-partial tours recursively from those for S-{s}.
(4) the method from (3) can require a lot of memory to store
the temporary files with S-pathstructures when S is growing.
So we try to improve it by only computing the
S-pathstructures and numbers of partial S-tours with that pathstructure for
S={1} , S={1,2},..,S={1..n/2} and for
S={n},S={n-1,n},..,S={n/2+1..n} and then count the number of ways
how to join the two pathstructures into a full tour and suming
up the products over all pairs (p1,p2) where p1 is a S1-pathstructures
and p2 is a S2-pathstructure with S1={1..n/2},S2={n/2+1..n}
This is the method used in [McKay] and can also be used to
efficiently enumerate open tours with endpoints in one half.
However I'm not sure yet in which cases this is faster than the method in (3)
provided huge and fast memory and HD-space is available.
E.g. to enumerate all closed 8*8 tours, (4) takes about 50 hours
and requires 200MB of RAM on a 2.5GHz computer while
(4) takes -I guess- about 20 hours and requires two times 10GB of fast
HD-space on two physically different HDs (two heads) and
500 MB of RAM for caching the HD-accesses.
I have used this method to produce the counts on
http://magictour.free.fr/enum
but I haven't tested this yet for 8*8 tours.