|
|
A193346
|
|
Number of (directed) Hamiltonian paths on the n X n X n grid graph.
|
|
1
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A general purpose matrix-transfer method can be used to compute values up to a(4). Using a diagonal sweep from one corner to the opposite corner will help to reduce the number of states. - Andrew Howroyd, Dec 20 2015
Schram & Schiessel (see Links) quote a different result for a(4): 27747833510015886 undirected Hamiltonian walks, which would double to 55495667020031772 directed Hamiltonian walks. However, that number is not divisible by 8 and thus cannot be correct. - Arun Giridhar, Dec 15 2015
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 1, there is a trivial Hamiltonian path of length 0.
For n = 2, the 144 paths fall in three different equivalence classes. Two of the three classes can be derived by taking a Hamiltonian cycle on a cube and deleting a single edge. The third class is a spiral path that ends at the opposite corner from its starting point.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more,bref
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|