title: Algorithms to find the number of Hamiltonian paths in a graph
body: <p>I'm trying to solve a slightly modified version of the <a href="http://en.wikipedia.org/wiki/Hamiltonian_path" rel="nofollow">Hamiltonian Path</a> problem. It is modified in that the start and end points are given to us and instead of determining whether a solution exists, we want to find the <em>number</em> of solutions (which could be 0).</p>
  
  <p>The graph is given to us as a 2D array, with the nodes being the elements of the array. Also, we can only move horizontally or vertically, not diagonally. Needless to say, we can't go from one city to two cities because to do that we would need to visit a city twice. </p>
  
  <p>I wrote a brute force solution that tries all 4 (3 or 2 for nodes on the edges) possible moves at each node and then counts the number of solutions (which is when it reaches goal and has seen all the other nodes too), but it ran for ridiculous amounts of time on inputs of modest size (like, say a 7x7 array). </p>
  
  <p>I also thought of using <a href="http://en.wikipedia.org/wiki/Bidirectional_search" rel="nofollow">bidirectional search</a> since we know the goal, but this didn't really help, since we don't just want the fringes to meet, we want to also ensure that all the nodes have been visited. Moreover, it could be that when all nodes have been exhausted between the two fringes, they end in a way such that they can't be joined. </p>
  
  <p>I feel like there is something I don't know that's leaving me with only a brute force solution. I know that the problem itself is NP-complete, but I'm wondering if there are any improvements over brute force. Can someone suggest something else?</p>
  
  <p>--Edit--</p>
  
  <p>I mentioned that using bidirectional search doesn't really help and I'd like to clarify why I thought so. Consider a 2x3 graph with the top left and bottom right nodes being the start and goal respectively. Let the fringes for bidirectional search move right from start and left from goal. After 2 moves, all the nodes would have been visited but there is no way to join the fringes, since we can only go in one direction from one node. However, it might be possible to make the algorithm work with some modifications, as David pointed out in his answer below. </p>