## 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 2010 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 2010 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 2010 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 2010 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 2010 at 23:59
show 1 more comment

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

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/… – Nathann Cohen Aug 22 2010 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 2010 at 0:03