Previously on this blog:

• “Polycube snakes and ouroboroi” (2022-11-18)
• “Polyomino strips, snakes, and ouroboroi” (2022-12-08)

I’ve bought enough Lego bricks to play around with polycube snakes in real life (just in time for Christmas!). Here are some curiosities I’ve constructed so far.

---

Back in 2019, Roy van Rijn investigated the maximum length of a snake packed into an \(m\times n\) rectangle (“The longest maze/snake,” January 2019; OEIS A331968 is related). Recently he made a neat JavaScript visualizer for 3D snakes packed into \(n\times n\times n\) cubes: 3x3x3, 4x4x4, 5x5x5, 6x6x6, 7x7x7. Here’s a Lego model of his 36-cell 4x4x4 snake.

---

I conjecture that the smallest ouroboros enclosing a “pseudo-tunnel” (as defined here) is this picturesque heart-shaped ouroboros with \(n=22\):

The cubes on the border of the pseudo-tunnel can be popped up or down in four different ways. Manipulating even further gives a “crumpled heart”: a 22-cube ouroboros with a “corner-type” pseudo-tunnel. Here are two copies of that ouroboros, built with the studs on opposite faces.

Can you produce any shorter ouroboros with a pseudo-tunnel?

---

I was surprised to find, in the output of my snake-enumerating program, that the number of one-sided non-ouroboros snakes with cavities was (so far) always twice the number of free non-ouroboros snakes with cavities; that is, my program was claiming that all non-ouroboros snakes with cavities were chiral (up to \(n=18\), at least). So I went and manually constructed a 22-cube non-chiral non-ouroboros snake with two cavities. The green snake was initially built as a mirror image of the red snake; but flipping the green snake upside-down makes it a translated copy of the red snake instead.

Martin Gardner presents a much simpler example of a “shape that has no plane of symmetry yet can be superimposed on its mirror reflection” in his Mathematical Games column of June 1981 (archive.org, JSTOR). Personally I find these shapes hard to wrap my head around, even when I’m seeing them in real life.

Is this the shortest non-chiral cavitous non-ouroboros snake, or can you find a shorter one? (The “non-ouroboros” part is key, since it’s not hard to find a mirror-symmetric cavitous ouroboros of length 12.)

Is this the shortest snake with two cavities?

Can you produce a non-chiral non-ouroboros snake (of any length) with only one cavity?

---

What is the shortest ouroboros with both a tunnel and a cavity? Both a pseudo-tunnel and a cavity?

---

Ever since I decided to classify snakes by whether they had cavities or no cavities, my C++ program has spent most of its CPU cycles trying to figure out if each snake has a cavity or not. I have thought of two algorithms and two quick-reject heuristics:

• Find the bounding box of the snake, add borders on all six sides, and flood-fill starting from one corner. If the flood-fill reaches all (volume - n) empty cells, the snake is cavity-free.

• Or: Find the “perimeter” of the snake, consisting of the 24 or 25 empty neighbors of each occupied cell. Deduplicate and flood-fill. If the flood-fill reaches all (volume - n) empty cells, the snake is cavity-free.

• A “deflated” snake can’t have cavities: If the snake’s bounding box is less than 3 units in any dimension, the snake must be cavity-free.

• A “mostly straight” snake can’t have cavities: If the snake’s bounding box is greater than n - 8 units in any dimension, the snake must be cavity-free, because it takes 8 cubes to “tie a knot” around an empty cell in the middle of a straight snake. In the picture below, 9 green cubes enclose a single empty cell; this is an 18-cube snake in a 3x3x10 bounding box.

  

• A “mostly straight” snake can’t have cavities, round 2: If the snake has fewer than 6 turnings, then it must be cavity-free. In fact I think any cavitous snake must have at least seven turnings; but I have no hard proof of that conjecture.

The quick-reject heuristics all suffer from the problem that the overwhelming majority of lengthy snakes are neither “deflated” nor “mostly straight.” It would sure be nice to find a faster way to tell whether a snake has cavities or not.

---

UPDATE, still 2022-12-11: Right after finishing this post, I realized a much better quick-reject heuristic than any of the above. Every cavity must have a “southwest bottom corner,” i.e., an empty cell which is the north neighbor of a snakey cell and the east neighbor of a snakey cell and the upstairs neighbor of a snakey cell. So, make a list of all the north, east, and upstairs neighbors of each snakey cell, sort it (to sort duplicates together), and check whether any entry is repeated three times. If so, you might have a cavity; if not, you definitely do not have a cavity.

The same check can be repeated for the “northeast upper corner,” the “northwest bottom corner,” and so on. The first two checks also serve to compute some of the “perimeter” of the snake, all of which is needed as input to the flood-fill algorithm in the second bullet above.

Since the majority of snakes do not have “corners” of all eight types, this heuristic lets us skip the rigorous cavity search in just about all cases. (Puzzle: How effective is this heuristic as \(n\) approaches infinity? Is there an \(n\) above which the majority of snakes do have corners of all eight types?)