# How many ways can a snake lie?

This is essentially a question about counting nonintersecting short paths in a cubic lattice, but with a twist. (One constraint that I did not make clear below is that when to turn is already chosen: after you have made the $n$th choice of perpendicular direction, you go a predetermined integer distance $a_n$ in that direction before making the next orthogonal turn. For a given $n$ and sequence $a_n$ of positive integers, I want to know how many paths there are.) Specifically I am wondering what combinatorial means there are to ensure counting paths that don't cross themselves. To focus efforts, I will describe a puzzle.

Take an integral brick ($3\times3\times3$ inspired this question) to be cut up in unit cubes. Choose a Hamilton path which visits every unit cube once, and then cut into unit cubes, drill a hole through all but two of them in a certain fashion, thread them with a rubber band, and then reassemble so that the rubber band nicely traverses the chosen hamilton path. (If you actually build one out of wood, I recommend two-coloring the cubes so that the path goes through alternating colors of cubes.) Congratulations! You now have a snake puzzle!

In the construction of this, you will usually have cubes with bends (the hole enters through one face and exits an adjacent face) and maybe cubes without (enter a face and either leave through the opposite face or don't leave). If $b$ is the number of cubes with bends, you can twist the configuration next to a bend to get up to four possible orientations of one part of the snake to the other. So there are up to $4^{b-1}$ possibilities in theory for reshaping the snake, of which one of these is an integral brick.

But not quite. The cubes are solid and only one of them can occupy a given lattice point; we count only feasible configurations where each cube is on a lattice point. Further, the band can take a lot of twisting but not much stretching: it must make a nice Hamilton path through the configuration of adjacent cubes and not change the order in which the cubes are visited. Finally those cubes without bends (there are $a_n - 1$ of them after the $n$th bend and before the next bend) serve a geometric but not combinatoric function directly: You can spin the cubes around the band and not affect the configuration. If the original path passed straight through a cube however, every feasible configuration will have a $1$ by $3$ (or longer) subsegment involving that cube. Likewise cubes that were bends in the path remain as bends in every feasible configuration. Let me not forget that the cubes are axis aligned and adjacent in each configuration.

Is there a way to count how many feasible configurations there are in such a puzzle? Once $b$ reaches $3$, there are possibilities for self intersection, so one does not get all $16$ possibilities sometimes. For the $3\times3\times3$ brick, which paths produce the largest (smallest) number of configurations, up to rotational and reflectional symmetry? Note that the band is flexible enough that I assume cubes pass through (or around) one another in moving from one feasible configuration to the next. As above, I am interested in the combinatorial technique that eliminates or accounts for the infeasible configurations that are tantamount to self-intersecting lattice paths.

Pointers to the literature are welcome, even to minor variations on this puzzle.

• "Choose a hamilton path which visits every unit cube once...." I am familiar with Hamiltonian paths as a concept in graph theory, but you haven't described a graph. Jun 12 '14 at 7:08
• @GerryMyerson: His graph appears to connect each cube to its up-to 6 face-to-face neighbors. Jun 12 '14 at 11:34
• OEIS A096969 counts the "number of ways to number the cells of an $n \times n$ square grid with $1,2,3,\ldots,n^2$ so that successive integers are in adjacent cells." That seems to count the Hamiltonian paths except on $\mathbb{Z}^2$ rather than $\mathbb{Z}^3$. Jun 12 '14 at 11:57
• Self-avoiding walks in a cubic lattice have been studied but I haven't found an explicit count. Here is one place where such a count might be recorded were it available. Jun 12 '14 at 11:58
• @Gerry, sorry for the lack of clarity. Joseph has the idea: let G be a grid graph or subgraph of N^3 lattice graph containing a rectangular region of vertices, a times b time c, and choose a hamilton path through G, which path will be reshaped in certain ways later. The object corresponding to this path is the cube and rubber band construction I call a snake, which will fold up into an a by b by c integral brick. Jun 12 '14 at 15:43