Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks in advance

share|improve this question
1  
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
3  
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

1 Answer 1

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

alt text
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}

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.