# Algorithm to generate self-avoiding random walk on a lattice

Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More specifically, how can I find a random hamiltonian path on a large $2^n \times 2^n$ or $2^n \times 2^n \times 2^n$ grid graph?

The distribution doesn't have to be completely uniform, however in general the lattice should look wrinkled. The method used to generate the path should have low probability of producing extremely long stretches of straight line.

• It's fine to ask about an algorithm on here. But software recommendation is off-topic. Also, you could put more effort into 1. defining your problem more rigorously 2. showing your attempt at answering your question. Jul 17, 2017 at 19:16
• For example, do you mean random Hamiltonian path on grid graph? Jul 17, 2017 at 19:25
• Yes; that's exactly what I meant. Jul 17, 2017 at 19:28
• And since it's a random generation. Do you care if a particular path is more likely to get generated than others? i.e. Do you need uniform chance for each path possible? (uniform chance will likely be harder to do.) Jul 17, 2017 at 19:40
• What exactly are the requirements on the distribution? You say you don't need a uniform distribution. So are you OK with an algorithm that outputs any hamiltonian path (even if it's always the same one)? If not, specifically what are the requirements? Also, can you be more precise about the class of graphs you want to handle? Finding a hamiltonian path on a grid graph is NP-hard in general, though it sounds like your graph might come from a more restricted class of graphs.
– D.W.
Jul 17, 2017 at 22:15