I'm looking for an efficient algorithm that is able to find an as random as possible Hamiltonian path in a bidirectional N*M grid.
Does anyone know where I can find, or how to go about constructing such an algorithm?
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. Space-filling curve http://img593.imageshack.us/img593/8060/sfc.png Image taken from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf
You can start with the approach you mentioned to find a Hamiltonian path. To further randomize the solution you can start rotating edges as mentioned on the wiki. Doing this more often will make the solution more random. Rotating a random edge N*M times keeps the algorithm in the efficient realm, while making the found Hamiltonian path more random.
