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?
How can you determine if this grid graph has holes?
Thanks in advance.
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?
How can you determine if this grid graph has holes?
Thanks in advance.
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.]}
{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}