11
$\begingroup$

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:

Partial Hamiltonian path

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).

$\endgroup$
  • 5
    $\begingroup$ Choosing randomly among the directions which allow a Hamiltonian continuation is not the same thing as choosing uniformly from the Hamiltonian paths. $\endgroup$ – Douglas Zare Sep 20 '14 at 2:17
  • 5
    $\begingroup$ check out this implementation, and do read the technical details and the linked preprint for more details on why sampling the Hamiltonian paths uniformly is challenging lattice.complex.unimelb.edu.au/hamiltonian_path.html $\endgroup$ – Yoav Kallus Sep 20 '14 at 4:36
  • 2
    $\begingroup$ As far as I know, this is more suitable to math.SE; however I don't fully understand the details of the question: why do you want randomness (and is it mandatory?)? Why do you want a path (rather than a tree), and is it mandatory? $\endgroup$ – Benoît Kloeckner Sep 20 '14 at 6:28
  • $\begingroup$ I think the underlying question looks interesting, thus I certainly don't vote to close. Though I think the text should be rewritten, to avoid hiding the mathematical problem behind a programming question. $\endgroup$ – Stefan Kohl Sep 20 '14 at 8:50
  • 8
    $\begingroup$ I think it is a natural and surprisingly difficult question to determine whether a path in a grid can be extended to a Hamiltonian path, or in roughly how many ways. If I'm missing an easy way to solve the problem, please enlighten me. I voted to reopen this question. $\endgroup$ – Douglas Zare Sep 20 '14 at 19:10
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Here is a snapshot of Nathan Clisby's generator, as cited by Yoav Kallus:


enter image description here

$\endgroup$
  • 1
    $\begingroup$ I tried that generator for a grid size of 200, and saw some artifacts that I don't believe are general. I think the algorithm used does not choose a path that is close to random for large grids. $\endgroup$ – Douglas Zare Sep 20 '14 at 18:12
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, but honestly I lost you already at the point where you said Since the path starts at an odd number it has to end at an even number. In this example the path actually starts at an odd number and ends at an odd number as well. I must honestly say that I don't have too much time right now to look further into your answer, this is just my first impression $\endgroup$ – Prutser Sep 21 '14 at 10:15
  • 1
    $\begingroup$ @Pruster: The point is that your labels are arbitrary, and if you relabel your image by reversing every second row, then the numbers give a parity invariant. That might help you construct a simple argument. It's courteous to read all of an answer before dismissing it, or at least the sentences leading up to the one you disagree with. $\endgroup$ – Zack Wolske Sep 21 '14 at 15:08
  • $\begingroup$ @The Masked Avenger: Your argument can continue to solve the example. Any path through 24-32-33-41-40 has to continue to 48-56-57-49-50 (since it can't stop at either 56 or 49), and that point leads to the contradiction. It can only continue to one of 42 or 58, so the other must be the end point, which it can't be because of parity. $\endgroup$ – Zack Wolske Sep 21 '14 at 15:32
  • $\begingroup$ Indeed, I thought @Prutser might see that and work out a generalization. The relabelling makes such reasoning easier for me to do by hand. $\endgroup$ – The Masked Avenger Sep 21 '14 at 15:52
  • $\begingroup$ I didn't dismiss this answer, I was just saying that I was in a hurry yesterday so I just had a minute to look into it. It wasn't my intention to entirely disagree with it all at once. I'm sorry that I made my comment look like that $\endgroup$ – Prutser Sep 21 '14 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.