# efficient way to count hamiltonian paths in a grid graph for a given pair of vertices

1/ What algorithm would you use to count all the hamiltionian paths in a n x m grid graph (n and m <10) from a given starting vertice to an ending one

2/ if this grid graph have holes?

-
On such a small graph, even the most naive algorithm would be fast, so I wouldn't bother with efficiency (unless you're trying to do this by hand!) –  Thierry Zell Aug 22 '10 at 13:18
@Thierry Zell: Is that true? Setting n=m=9 yields a graph with 81 vertices and maximum degree 4, and I am not so sure that naive algorithms will be fast for graphs of this size. –  Tsuyoshi Ito Aug 22 '10 at 16:53
Then answer is sometimes zero. Color the vertices like a chessboard. If there are an odd number of vertices you can't start and end on a white vertex. –  Emil Aug 22 '10 at 18:13
Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter, "Hamilton Paths in Grid Graphs," SIAM J. Comput. Volume 11, Issue 4, pp. 676-686: "...we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes." –  Joseph O'Rourke Aug 22 '10 at 19:24
I think I remember having been told the Hamiltonian Path problem was NP-Hard on subgraphs of grids... If you are interested in this, I know who to ask for references. Your question is about computing the number of them, so it's not an answer but I thought I may mention it, just in case ... –  Nathann Cohen Aug 22 '10 at 23:59

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[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.]}


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}
`
-
Would you by any chance know how the Hamiltonian Path problem is solved in Mathematica ? I found the source of the Combinatorica package [1], and the HamiltonianPath seems to call the HamiltonianCycle function, but I have to admit I do not really understand what is going on in this function. It looks too short to be anything more complicated than a bruteforce enumeration, but I am having a very hard time with their syntax ^^; THanks [1] cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m –  Nathann Cohen Aug 22 '10 at 23:57
@Nathann: Sorry, I don't know offhand, but I suspect Combinatorica follows F. Rubin, "A Search Procedure for Hamilton Paths and Circuits," J. ACM 21, 576-580, 1974. –  Joseph O'Rourke Aug 23 '10 at 0:03