What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?

Question

A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,

A  0  0  0

0  0  0  0

0  0  C  D

What are some effective heuristics that could be applied to find them - and particularly, techniques to trim/discard paths along the way?

Edit: Just to clarify, the edges are formed when elements are connected horizontally and vertically, but not diagonally. The problem also states that any element that is marked 0 can be used to form a path, but non 0 elements are "obstacles" that need to be avoided.

A-0-0-0
      |
0-0-0-0
|
0-0-C D

could be one path, for instance. Another may be,

A 0-0-0
| |   |
0 0 0-0
| | |
0-0 C D

Answer 1

I don't see an easy way of counting without enumerating. You can easily visit all hamiltonian paths with an exaustive depth-first search with backtracking. You can actually cheat a bit, and realize that, if N is the number of hamiltonian paths that start by going to the right, the total number of hamiltonian paths is 2N (due to the symmetry if the grid). This does not extend all the way (for some vertices not all paths will lead to the same number of cycles, but you can upper bound the number of hamiltonian paths easily with a similar argument (with the bonus that you can solve parts of it exactly to improve your bound with symmetry arguments). This is the strategy I'd choose.

But if you don't want this, some generic heuristics:

• You can also easily upper bound the number of hamiltonian paths as |E| choose |V|-1 (where |E| is the number of edges and |V| the number of vertices in the graph), which can be a lot better for a sparse graph than |V|! (the naive bound that assumes that the graph is complete).

• An easy way to improve this bound is by trimming known-bad combinations, by not considering twice edges from the same vertex. So you'd get something like prod_v(deg_v-1) (which should still upper bound the number of hamiltonian paths, since you're now counting cycles more than once, I think).