I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and then validate whether it is still possible to complete the current path to visit each square exactly once. This step will be undone if the extension is impossible and one of the other free directions will be tried. How can we determine if it is possible to extend the path to a Hamiltonian path?
Here is an example where no simple invariant seems to detect the lack of a Hamiltonian extension:
We are at cell 25 and we have three possibilities: 17, 24 and 33. The path will eventually fail if you go to cell 17. (In the linked page, you can mark the white cells by clicking on them, if you want to try things out).