<p>This paper describes a method:</p>

<p>Oberdorf, R.; Ferguson, A.; Jacobsen, J.L.; Kondev, J. - <a href="http://arxiv.org/abs/cond-mat/0508094" rel="nofollow">Secondary Structures in Long Compact Polymers</a> (arXiv.org)</p>

<p>The method roughly consists of the following: start with a zig-zag pattern (a non-random Hamiltonian path on the grid) and repeatedly apply a transformation (called "backbite") to the path. A backbite consists of adding an edge from one of the endpoints A to an adjacent vertex B other than the one A is connected to (thus creating a loop), and then remove the edge that starts in B that is not the one just added and that causes a loop (there will always be only one causing a loop other than the one just added).</p>

<p>The authors add some conditions to obtain rough uniformity (including an estimation on how many times to apply the backbite move). Details in the paper.</p>

<p>The authors also prove empirically that the probability of their method generating adjacent endpoints approximately matches the theoretical probability in uniform random Hamiltonian paths.</p>

<p>There is an implementation of the algorithm in JavaScript here: <a href="http://lattice.complex.unimelb.edu.au/hamiltonian_path.html" rel="nofollow">Hamiltonian Path Generator</a></p>
Algorithm to find a random Hamiltonian path in a grid?
<p>I'm looking for an efficient algorithm that is able to find an as random as possible <a href="http://en.wikipedia.org/wiki/Hamiltonian_path" rel="noreferrer">Hamiltonian path</a> in a bidirectional N*M grid.</p>

<p>Does anyone know where I can find, or how to go about constructing such an algorithm?</p>

<hr>

<p>I've already found an efficient approach (see image below). The end result here is a Hamiltonian cycle. Removing a random edge will make it a Hamiltonian path. This algorithm is efficient, but does not provide enough randomness. This approach will always have the begin and end point of the path right next to each other, while I'd like to have those in random locations.
<a href="http://img593.imageshack.us/img593/8060/sfc.png" rel="noreferrer">Space-filling curve http://img593.imageshack.us/img593/8060/sfc.png</a>
Image taken from <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&amp;rep=rep1&amp;type=pdf" rel="noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&amp;rep=rep1&amp;type=pdf</a></p>