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.





Grid size:       Quality factor:       Circuits only:

Canvas element not supported in your browser.



Technical details: