A193346 Number of (directed) Hamiltonian paths on the n X n X n grid graph.

1, 144, 4960608, 55493434415544000

Offset: 1

Author

Eric W. Weisstein, Jul 23 2011

Keywords

• nonn
• hard
• more
• bref

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

Examples

			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.
		

Links

• Raoul D. Schram and Helmut Schiessel, Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 46 (2013), 485001.
• Raoul D. Schram and Helmut Schiessel, Corrigendum: Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 49 (2016), 369501.
• Jamie Shepard, Solvability and Difficulty of the Snake Puzzle in the Cube and its Topological Variants, Honors Thesis, Andrews Univ. (2024) Art. No. 290.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Hamiltonian Path
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

Cf. A003763, A096969.

Extensions

a(4) from Andrew Howroyd, Nov 15 2015

a(1) corrected by Arun Giridhar, Dec 20 2015