Algorithms to find the number of Hamiltonian paths in a graph

I'm trying to solve a slightly modified version of the Hamiltonian Path 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 number of solutions (which could be 0).

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.

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

I also thought of using bidirectional search 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'开发者_如何学Got be joined.

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?

--Edit--

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.

According to Wolfram Alpha,

... the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

I believe you would want to start by finding a single hamiltonian path, and then splitting it into two paths, making the split point one that clearly separates the two paths as much as possible. Then you can find the permutations in the subgraphs (and recurse, of course!)

I don't know the exact algorithm, but that sort of divide and conquer method is where I would start.

Someone asked a question very similar to yours over on Math Overflow at https://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given-pair-of-vert and (1) they didn't get a deluge of "here's how to do it efficiently" responses (which probably means there isn't an easy way), (2) Mathematica apparently takes 5 hours to count the paths between opposite corners on a 7x7 grid, so you may well not be doing anything very wrong, and (3) there are a few interesting pointers among the answers.

You could still use a bidirectional search, just add a constraint to the search so that previously seen nodes will not be candidates for searching.

Another approach you could take which would lend itself to a paralellizable solution is to break the search into smaller searches.

For example, try to solve your original problem by solving:

For each node, n, which is not a start or end node, find all paths from the start to n (set1) and from n to the end (set2).

After you find set1 and set2, you can discard all elements of their cross product which have a common node other than node n.

On a 7x7 array (i.e. a total of 7*7=49 nodes), having either a O(n!) algorithm or a O(2^n*n^2) algorithm will both take way too much time.

Perhaps there is some way speeding this up taking into account the special characteristics of this particular graph (e.g. each node has at most 4 edges), but a fast solution seems improbable (unless someone incidentally finds a polynomial time algorithm for the Hamiltonian Path problem itself).

It can be solved using DP with bitmasking for values of n upto 20 or a few more i guess. Create a 2d dp table. dp[i][j] represents the answer of case that you are on ith vertex and j stores the information about visited vertices.Here's a C++ code.

Macros used:

#define    oncnt    __builtin_popcount
typedef    vector<int>   vi;

Outside Main:

vi ad[21];
 int n,m;

 int dp[20][(1<<19)+1];

int sol(int i,int mask)
{
    //cout<<i+1<<" "<<oncnt(mask)<<"\n";

    if(i==n-1)
    return 1;

    if(mask&(1<<i))
    return 0;

    int &x=dp[i][mask];
    if(x!=-1)
    return x;

    x=0;

    for(int j=0;j<ad[i].size();j++)
    {
        int k=ad[i][j];
        if(mask&(1<<k))
        continue;
        if(k==n-1&&oncnt(mask)!=n-2)
        continue;
        if(k!=n-1&&oncnt(mask)==n-2)
        continue;
// The above two pruning statements are necessary.
        x=madd(x,sol(k,mask|(1<<i)));

    }

    return x;

}

Inside Main:

cin>>n>>m;

for(int i=0;i<=n-1;i++)
 {
    for(int j=0;j<=(1<<(n-1));j++)
    dp[i][j]=-1;
 }


int a,b;
for(int i=1;i<=m;i++)
{
    cin>>a>>b;
    a--;
    b--;
    ad[a].pb(b);
}


 cout<<sol(0,0);

I found this approach to be extremely fast, and I was able to generalize it to work on a hexagonal grid: https://hal.archives-ouvertes.fr/hal-00172308/document. The trick is to push a frontier through the grid while keeping track of the possible paths. My implementation handles 20x20 grids in a few seconds.