Square filling self avoiding walk 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). 
 A: The following paper by Umans and Lenhart gives a polynomial-time algorithm for finding a Hamiltonian cycle in "solid" grid graphs (grid graphs with no holes with area larger than $1$):
http://users.cms.caltech.edu/~umans/papers/LU97.ps
For general grid graphs, the problem is NP-complete. 
Even though they search for cycles and not paths, the algorithm might be useful, since a complement of a path in a grid is either disconnected (which is easy to detect) or has at most one large hole. 
A: Here is a snapshot of Nathan Clisby's generator,
as cited by Yoav Kallus:


A: You can use parity and some constraints to help with the analysis.   Lets reverse the numbering on
 some rows so that neighboring squares have opposite parity.  Since the path starts at an odd
number it has to end at an even number.  Thus the path does not stop at
squares 33 or 24 in your diagram (33 and 31 in mine).  You can then
show that a path must visit 24 33 and 40 in that order or the reverse
order, (I call 40 number 47). This can be extended by hand to rule out
many squares as stopping points.
There are puzzles called Slitherlink which use hamiltonian cycles.  Likely their designers can give you
some suggestions for seeing if an extension works.
