[Math] Efficient way to count Hamiltonian paths in a grid graph for a given pair of vertices

co.combinatoricsgraph theory

  1. What algorithm would you use to count all the Hamiltionian paths in a $n \times m$ grid graph ($n$ and $m<10$) from a given starting vertex to an ending one?

  2. How can you determine if this grid graph has holes?

Thanks in advance.

Best Answer

Here is Mathematica code that finds all the Hamiltonian paths between opposite corners of a $5 \times 5$ grid graph:

<< Combinatorica`;
n = 5;
G = GridGraph[n, n];
(* Add dangling edges to corners to force start/end vertices *)
Gplus = AddVertex[G, {0, 0}];
Gplus = AddVertex[Gplus, {n + 1, n + 1}];
Gplus = AddEdge[Gplus, {1, n^2 + 1}];
Gplus = AddEdge[Gplus, {n^2, n^2 + 2}];
ShowGraph[Gplus]
H = HamiltonianPath[Gplus, All];
Print["Number of paths=", Length[H]];
Print["Paths=", H];
Number of paths=208
Paths={{26,1,2,3,4,5,10,9,8,7,6,11,12,13,14,15,20,19,18,17,16,21,22,23,24,25,27}, [etc.]}

GridGraph

Addendum. Setting $n=7$ to compute the comparable number for a $7 \times 7$ grid returns 223,424 Hamiltonian paths between opposite corners. [5 hrs computation time on a 2.5GHz laptop.] The first one returned is: 

{50, 1, 2, 3, 4, 5, 6, 7, 14, 13, 12, 11, 10, 9, 8, 15, 16, 17, 18,
19, 20, 21, 28, 27, 26, 25, 24, 23, 22, 29, 30, 31, 32, 33, 34, 35,
42, 41, 40, 39, 38, 37, 36, 43, 44, 45, 46, 47, 48, 49, 51}
Related Question