Cube Snake Puzzle

[lpetrich]

I was recently given a cube-snake puzzle. It consists of 27 cubes that can rotate relative to each other. Some cubes have neighbors on opposite sides, while most of the others have neighbor at a 90-degree angle. Not surprisingly, two cubes have only one neighbor.

With the puzzle's arrangement of neighbors, there is only one solution to within rotations and reflections.


In the solution, the cubes form a 3*3*3 supercube, and their arrangement forms a "Hamiltonian path", named after 19th cy. mathematician William Rowan Hamilton, the discoverer of quaternions. He proposed an "icosian game", finding such a path among the vertices of a dodecahedron.

If a Hamiltonian path's ends are neighbors, then they can be connected to make a Hamiltonian cycle.


I decided to see how many different 3^3 cube snakes that one can construct. I wrote a brute-force searcher, and in about a minute of CPU time, I found 4960608 solutions, counting over all possible source and destination cubes. Splitting up by cube type, I found:

• Vertex - neighboring vertex: 31164 - 12
• Vertex - across-face vertex: 36372 - 12
• Vertex - across-cube vertex: 38256 - 4
• Vertex - neighboring face: 21880 - 24
• Vertex - far face: 28708 - 24
• Face - neighboring face: 19668 - 12
• Face - opposite face: 22240 - 3

That's 198288 solutions to within rotations, reflections, and reversals, and 2480304 to within reversals.

So there are a lot of possible 3^3 cube snakes.

 

[lpetrich]

Notice that all these cube snakes start and end at vertices and face centers. This is easy to see from a party argument. Give a corner cube parity +1 and reverse the parity for going along an edge to a neighboring cube. The edge centers thus have parity -1, the face centers parity +1, and the center parity -1.

My cube snake illustrates this parity by making the +1 cubes dark wood and the -1 cubes light wood.

There are thus 8 v's + 6 f's = 14 of +1 cubes and 12 e's + 1 c = 13 of -1 cubes in a snake.

It is easy to show that a cube snake (Hamiltonian path) can only start and end at +1 parity cubes: vertices and faces.

It's very evident that there are no Hamiltonian cycles. That is because the paths do not end in neighbors.


For calculating these numbers, I needed to look at generalizations of this problem, and I found some.

A193346 - OEIS - Number of (directed) Hamiltonian paths on the n X n X n grid graph.

1, 144, 4960608, 55493434415544000

"A general purpose matrix-transfer method can be used to compute values up to a(4). Using a diagonal sweep from one corner to the opposite corner will help to reduce the number of states. - Andrew Howroyd, Dec 20 2015"

In general, for odd n, all the corner cubes have the same parity, and a path's ends are at cubes with that parity. None of them form cycles.

For even n, the two ends of a path have opposite parities, and cycles may exist.

Generalizing to rectangular solids, these conclusions hold for odd and even numbers of cubes, respectively.

 

[lpetrich]

For the 2^3 case, I find

• Neighboring cubes: 4 - 12
• Opposite cubes: 6 - 4

The neighboring-cube paths are two inequivalent ones multiplied by reflections across the cube. They can be made by splitting the Hamiltonian cycle, only one to within the 3 R's. Those 3 R's give a multiplicity of 24.

The opposite-cube paths are spirals around the cubes between the end cubes. The 6 is from 3 rotations and 2 reflections.

Adding them in,

• Neighboring cubes: 2 - 2 - 12
• Opposite cubes: 1 - 6 - 4

That gives 3 distinct ones.

For the 3^3 case,

• Vertex - neighboring vertex: 15582 - 2 - 12
• Vertex - across-face vertex: 18186 - 2 - 12
• Vertex - across-cube vertex: 6376 - 6 - 4
• Vertex - neighboring face: 10940 - 2 - 24
• Vertex - far face: 14354 - 2 - 24
• Face - neighboring face: 9834 - 2 - 12
• Face - opposite face: 2780 - 8 - 3

Total: 78052 - still a lot of cube snakes

 

[lpetrich]

Scaling down to the 2D case, OEIS has a lot more results. The 2D version of this problem:

A096969 - OEIS - Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in adjacent cells (horizontally or vertically).

1, 8, 40, 552, 8648, 458696, 27070560, 6046626568, 1490832682992, 1460089659025264, 1573342970540617696, 6905329711608694708440, 33304011435341069362631160, 663618176813467308855850585056, 14527222735920532980525200234503048

"Number of directed Hamiltonian paths in (n X n)-grid graph. - Max Alekseyev, May 03 2009"

The parity arguments for 3D also apply for 2D.

For the 2^2 case, there is only one path, and for the 3^2 case, two paths: corner - corner and corner - center.

For Hamiltonian paths,

A143246 - OEIS - Number of (directed) Hamiltonian circuits in the n X n grid graph.

A003763 - OEIS - Number of (undirected) Hamiltonian cycles on 2n X 2n square grid of points.

1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106

Undirected: clockwise and counterclockwise directions counted together; directed: separately

There are no cycles for size (odd)^2.

[1402.0545] Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs - counts to within the three R's - rotation, reflection, and reversal

 

[lpetrich]

A096970 - OEIS - Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in the same row or column.

1, 8, 1512, 22394880, 50657369241600, 28606505102329400524800, 5959275438217048853558620520448000

"For n >= 2, number of (directed) Hamiltonian paths on the n X n rook graph. - Eric W. Weisstein, Dec 16 2013"

One can go as much as one wants along either axis.

-

A158651 - OEIS - Number of directed Hamiltonian paths on the n X n king graph.

1, 24, 784, 343184, 729237344, 13089822163800, 1659110130720710584, 1635069460917798701270872, 12308784500036123518164726610224, 721833220650131890343295654587745095696, 330596986686626406483380599328509951896788808144

Number of open directed king's tours on the n X n board.

A140521 - OEIS - Number of directed "king tours" on an n X n board.

A140519 - OEIS - Number of (undirected) Hamiltonian cycles on the n X n king graph.

1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418

Meaning that one can go one square diagonally as well as axially.

 

[lpetrich]

A001230 - OEIS - Number of undirected closed knight's tours on a 2n X 2n chessboard.

0, 0, 9862, 13267364410532

"No closed tour exists on an m X m board if m is odd." - that's from parity

This is making a knight visit every square on a board exactly once and then return to its starting square.

 Knight's tour - an old chess conundrum