Recently I was reminded of an old blogpost I wrote about packing a snake-like path into 2D space (https://www.royvanrijn.com/blog/2019/01/longest-path/).
I never bothered to research this; try to find the 'optimal' ways to do this in, for example, a 2D square. Has this been done before?
Last week somebody asked me about packing such a 'snake' in 3D polycubes. So I quickly wrote some (inefficient) code this morning to check and found these 3D-snakes:
I believe these are optimal:
- 2x2x2: length 5
- 3x3x3: length 16 (https://www.royvanrijn.com/polycube/3x3x3.html)
- 4x4x4: length 36 (https://www.royvanrijn.com/polycube/4x4x4.html)
These I haven't exhaustively checked:
- 5x5x5: length 65 (https://www.royvanrijn.com/polycube/5x5x5.html)
- 6x6x6: length 102 (https://www.royvanrijn.com/polycube/6x6x6.html)
- 7x7x7: length 156 (https://www.royvanrijn.com/polycube/7x7x7.html)
Is this something that has been researched, if so: what is the correct terminology and where could I find more information? Can we easily find bounds?
I tried to find information on this packing on things like the OEIS, but couldn't find anything yet.
Edit: I've updated the score and visualization of 5x5x5 and 7x7x7
The 2D m×n case seems to be asked and answered here: Longest path through a rectangular board
OEIS A331968, "Maximum number of unit squares of a snake-like polyomino in an n X n square box," is the answer for the n×n case specifically.
(I don't see anything obvious in OEIS for the m×n rectangular case, but OEIS isn't really built to represent two-dimensional charts/sequences; the best it can usually do is to list off the diagonals, or half-diagonals, or something like that.)
I don't see anything in OEIS dealing with the 3D cube n×n×n (or 4D hypercube, etc).
For fixed n and variable dimensionality, OEIS A099155 is the solution for the (2×2×...×2×2) hypercube, known as the "snake-in-the-box problem." OEIS A000937 is the "closed snake-in-the-box" or "coil-in-the-box" problem (or what I would call the "ouroboros-in-the-box problem").
Your spinnable solutions are very cool! They look very complicated/wiggly; I wonder if that's unavoidable, or if there exist equally lengthy solutions that are "less wiggly." For example, what if you look for long snakes but break ties (between two equally long snakes) by taking the one with the fewest cornerings/turnings. Does that produce more systematic-looking snakes?