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

Improve this question
$\endgroup$
7
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 19:10

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

enter image description here

Improve this answer
$\endgroup$
1
  • 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, 2014 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.

Improve this answer
$\endgroup$
8
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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