### Soul_Full_Of_Thunder's blog

By Soul_Full_Of_Thunder, history, 5 weeks ago, ,

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!

• +59

 » 5 weeks ago, # |   +11 Damn that's cool!!!
 » 5 weeks ago, # |   +36 what does non trivial means?
•  » » 5 weeks ago, # ^ |   +14 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.
•  » » 5 weeks ago, # ^ |   +19 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.
•  » » 5 weeks ago, # ^ |   +23 Here you can find how it was stated in the problem.
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   +21 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.
•  » » 5 weeks ago, # ^ |   +59 Your face after solving this problem.
•  » » 5 weeks ago, # ^ |   +17 We also gave a similar one (but harder) in one of our contests
 » 5 weeks ago, # |   0 How about tweaking Hilbert Curve? I think it can also give some interesting results.
•  » » 5 weeks ago, # ^ |   0 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 (ó﹏ò｡) .