Hamiltonian path generator

About: This javascript program generates a Hamiltonian path on an n × n grid using the backbiting move described in the paper "Secondary structures in long compact polymers" by Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen and Jané Kondev, Phys. Rev. E 74, 051801 (2006). Paper available via the APS (subscription required) or as a pre-print on the arxiv. The resulting path is displayed below both as an image and as a sequence of grid points. (Further technical details at the bottom of the page.)
Author: Program by Nathan Clisby, July 2012. Please let me know if you find this generator useful, or if you have any suggestions for improvement! (homepage, clisby@gmail.com)
History: The impetus to create this generator came from Daniel Crooks, an artist based in Melbourne, who needed a tool for generating long Hamiltonian paths. In his words: My original interest in the Hamiltonian paths was for a portraiture project. I've developed a process for taking large format photographs using a video camera and a robotic pan/tilt head to 'scan' the image of the sitter over time. As part of the research I became interested in Hamiltonian paths, firstly as a motion path for the camera and then subsequently the aesthetic and conceptual possibilities inherent in the paths themselves.
I had previously come across the aforementioned paper on sampling Hamiltonian paths, and took the opportunity to learn some javascript and create this generator. I hope to apply the expertise gained in this enterprise to other visualisation projects in combinatorics and statistical mechanics.
Usage: Specify desired grid size and choose `quality factor' which determines how `random' the path will be, then click "Generate Hamiltonian path" or reload page. Check "Circuits only" if you wish to only generate Hamiltonian circuits (read technical details at bottom of page to see why circuits are not selected uniformly at random).
Quality factor of 1.0 should be fine for most purposes; for large grids it may be worth trying 0.5 or even 0.1.
Tested on firefox and chrome browsers. N.B.: for large grids (say 100 × 100 or larger) you may be prompted to stop the script due to the long running time. For chrome, I found that if I did nothing the script would keep running in the background, whereas for firefox I would have to click "continue" for the script to complete.

Technical details:

• Running time(n × n grid) = (Quality factor) × 20 × n² log²n × Pr(success of backbite move) × (Expected CPU time for backbite move)
• The `quality factor' is an arbitrary constant, while the factor of 20 seems to ensure that Hamiltonian path with good randomness is achieved when quality factor is 1.
• The cover time for the simple random walk on an n × n grid is n² log²n (I've found this stated in a number of places, but if anyone could give me the original reference I would appreciate it). The Hamiltonian path endpoints perform something like a random walk on the grid, and so we use this as an approximation for the cover time. (It may be a tight bound, but I'm not an expert on this problem and can only say that it seems plausible that the bound is in fact tight.)
• The probability of success of the backbite move approaches 1 as n becomes large.
• I have not performed any testing to determine the mean CPU time for a backbite move, but it must be O(n²), and it is reasonable to suppose that in fact it is a relatively small power of n. A more sophisticated implementation would allow the backbite move to be performed in time O(log n).
• The Markov chain resulting from repeated application of the backbiting move has not (yet) been proved to be ergodic. This is an interesting open problem. The Markov chain is ergodic for small grid sizes, and my intuition is that the algorithm is extremely likely to be ergodic for arbitrary two-dimensional grids (it seems to me that if the set of Hamiltonian paths were to be disconnected this would be more likely to occur for smaller grids for which the grid boundary has greater influence). For three dimensions and higher I don't have any intuition because here large grids are intrinsically different to small grids due to the existence of knots.
• Hamiltonian circuit generator just generates a path, and continues iterating the backbiting move until a circuit is generated. This method cannot select a circuit uniformly at random because circuit selection probability is weighted by the (expected) space between samples. I think this can be best explained by an example: suppose we have a Markov chain to uniformly select elements 1 and 2 from a list of N elements. For each time step we can move up or down one element on the list with uniform probability; if this reaches 0 or N+1 the move is rejected. This Markov chain selects 1 and 2 with uniform probability, but if we look at the behaviour of the full chain the probability that we will sample 1 before 2 given an arbitrary starting time vanishes with increasing N as 1/N. This is because at the starting time we are almost surely in the interval [3,N], and in this case the next element must be a 2. This is an extreme example, and the Hamiltonian circuits generated here are likely to be statistically extremely similar to circuits generated from the uniform distribution, but the method used in this Hamiltonian circuit generator should most definitely not be used for serious numerical work.