Enumerating all hamiltonian paths from start to end vertex in grid graph
- by Eric
Hello,
I'm trying to count the number of Hamiltonian paths from a specified start vertex that end at another specified vertex in a grid graph. Right now I have a solution that uses backtracking recursion but is incredibly slow in practice (e.g. O(n!) / 3 hours for 7x7). I've tried a couple of speedup techniques such as maintaining a list of reachable nodes, making sure the end node is still reachable, and checking for isolated nodes, but all of these slowed my solution down. I know that the problem is NP-complete, but it seems like some reasonable speedups should be achievable in the grid structure.
Since I'm trying to count all the paths, I'm sure that the search must be exhaustive, but I'm having trouble figuring out how to prune out paths that aren't promising.
Does anyone have some suggestions for speeding the search up? Or an alternate search algorithm?