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

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

• Which are the edges in your example? – Alexandru Aug 16 '10 at 20:17
• Did this per chance come from Quora's jobs challenge page? quora.com/challenges – majelbstoat Jan 10 '11 at 10:20