<p>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.</p>

<p>But if you don't want this, some generic heuristics:</p>

<ul>
<li><p>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).</p></li>
<li><p>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).</p></li>
</ul>

CC BY-SA 2.5
2010-08-17T02:17:40.363Z
Can this not be improved to a kind of dynamic programming with memoization?
András Salamon
CC BY-SA 2.5
2010-08-16T21:41:22.647Z
2010-08-17T01:12:55.963Z
2010-08-17T01:12:55.963Z
Alexandre Passos
<p>A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,</p>

<pre><code>A  0  0  0

0  0  0  0

0  0  C  D
</code></pre>

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

<p>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. </p>

<pre><code>A-0-0-0
      |
0-0-0-0
|
0-0-C D
</code></pre>

<p>could be one path, for instance. Another may be,</p>

<pre><code>A 0-0-0
| |   |
0 0 0-0
| | |
0-0 C D
</code></pre>

CC BY-SA 2.5
2010-08-16T20:17:35.470Z
Which are the edges in your example?
Alexandru
CC BY-SA 2.5
2011-01-10T10:20:43.783Z
Did this per chance come from Quora's jobs challenge page?  http://www.quora.com/challenges
majelbstoat
<ds.algorithms><hamiltonian-paths>
What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?
viksit
# What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?

(Asked by: username_0 on 2010-08-16)

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

**Tags:** ds.algorithms, hamiltonian-paths
> **Comments:**
> **username_1**: Which are the edges in your example?  
> **username_2**: Did this per chance come from Quora's jobs challenge page?  http://www.quora.com/challenges  

---

## 1 answers

### Answer by username_3 on 2010-08-16. Score: 3 | Accepted answer

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

> **Comments:**
> **username_4**: Can this not be improved to a kind of dynamic programming with memoization?  

---

