MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 Added one of the H-paths.

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} 

2 n=7 results

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

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