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!
Damn that's cool!!!
what does non trivial means?
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.
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.
Here you can find how it was stated in the problem.
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.
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.
We also gave a similar one (but harder) in one of our contests
How about tweaking Hilbert Curve? I think it can also give some interesting results.
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 (ó﹏ò｡) .