Soul_Full_Of_Thunder's blog

Nontrivial Hamiltonian Cycle on 2D grid.
By Soul_Full_Of_Thunder, history, 4 years ago, In English

Two days ago, one of my friends (Danylo99) told me about a cool problem from a recent SIT contest. The goal was to find a nontrivial cycle that visits all cells on a 2D grid with even sides.

I thought it would be interesting to visualize the results.

Here is a slightly larger one. If anyone knows other approaches, please share :)

By the way, I also made a video of what's going on inside the algorithm.

Hope you all have a great day!

  • Vote: I like it
  • +59
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Damn that's cool!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

what does non trivial means?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Like you could easily snake back and forth and then on the first column go all the way up to the start. That would be trivial and show a fairly boring picture. This picture is more interesting.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Since there are no walls, I assume trivial paths are like spirals, or column-wise/row-wise snake patterns. I agree that a formal definition would be interesting.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Here you can find how it was stated in the problem.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think, general approaches are covered by Maze generation algorithm article from Wikipedia. Most of them may be utilised to solve the problem. I wonder though if there's a way to generate such cycles uniformly at random, as these approaches (including yours, I think) are a bit biased and usually there are cycles that they can't generate at all.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

If anyone wants to try a similar problem — printing a Hamiltonian path on a 2D grid that starts in given cell (or tell if it does not exist) here it is. Sounds easy right? But willingness to suffer is advised.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How about tweaking Hilbert Curve? I think it can also give some interesting results.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hilbert Curve nicely fills a square. So far I think you can just insert some squares anywhere in the image. But I lack the willingness to suffer (ó﹏ò｡) .

    → Reply