Miscellaneous Remarks, Ideas, Trials: Snake Cube

Last December, a young cousin of mine got a snake cube for Christmas. He showed it to me. Even though I have never seen that thing, I took a low pitched voice, hinted with a lot of self confidence that it was very easy to do/undo it. In the manipulation, I unfolded it and... was completely unable to fold it again into its original cube shape. I was a little bit ridiculous

and later decided that at least there is a good way to turn this domestic defeat into a learning experience: I should solve this snake cube.. No ! All snake cubes !! Forever !!!

Nothing difficult, of course, but the problem still requires to be approached in an organized fashion.

Introduction

A snake cube puzzle is a string of 27 cubes connected by an elastic that goes through each cube. The elastic goes either straight through the cube, from one face to the opposite, or turns inside the cube and goes from one face to an adjacent. The aim of the game is to fold it into a 3x3x3 cube, if possible. It is usually quite difficult to do it the first time, when a snake does not have many solutions.

Our objective here is to find all possible solution snake cubes (ignoring rotations and reflections), and sort them to try and make sense of how this population is distributed. To be more specific, any 2 snakes that are identical after a series of rotations and/or reflections are considered one solution.

A solution snake cube is an undirected Hamiltonian path in the 3x3x3 grid graph.

In order to explore the possibilities in an orderly and economical way, we first describe a method to travel inside the grid graph, starting from specific first few vertices all the way to Hamiltonian path. We try to avoid doing redundant searches. Indeed the cube has many symmetric axes, and many symmetric starting points. There are many possibilities to explore so this concern for optimisation is no luxury.

Once the search is complete, we sort the solution snake cube (the "paths") by letter sequence. A letter sequence is a string of 27 letters that define a snake cube puzzle.

E for and end cube.
S for a 'straight' cube; the elastic goes from one face to the opposite face.
C for a 'corner' cube; the elastic goes from one face to an adjacent face.

Within all the paths for one sequence, we determine the "base" paths, ie those which cannot be deducted one from the other by a combination of rotations and/or reflections ("transformations"). This step requires a lot of calculations so all transformation are computed beforehand.

Finally we get all the base paths and can examine the results.

The Search for Hamiltonian Paths

First we define the grid graph formally, label the vertices and give 3D coordinates.

Each vertex in the grid graph is associated to a point. The {x,y,z} axes are oriented so that the vertices at the bottom left far corner are at the origin and:

Note that here we do not seek to find all Hamiltonian paths but a subset of all Hamiltonian paths large enough to span all Hamiltonian paths through a combination of rotations/reflections. In other words, we want to be certain that any Hamiltonian path can be obtained from one of the subset through a combination of rotations/reflections.

Now we define the grid graph adjacency matrix. It will be used to determine where a path can go from one given vertex, for all vertices. We also create 2 slightly modified versions of the adjacency matrix. They will be used to constrain the range of possible next hops for path, in the cases where the forbidden next hops could only lead to the discovery of paths necessarily symmetrical to the allowed paths. In short they help keeping the otherwise very long computing time within reasonable boundaries.

An adjacency matric must be read as follows:

The j^th element in the i^th line is 1 when vertex i can lead to vertex j, 0 otherwise. In the normal adjacency matrix (adjMat), the matrix is symmetric as the graph is undirected.

In the slightly modified adjacency matrices, some edges are made forbidden (the yellow squares) so the matrix becomes assymetric. Those matrices are named adjMatE and adjMatF because they will be used in the case of a path starting from respectively a vertex on an edge, a vertex in a face.

Now we determine first few steps of the paths starting from

a corner (C)
an edge (E)
a face (F)
the center of the cube (M)

The first 2 paths starting from a corner (C) are determined (ie constrained) as long as a choice on the way only does not leave out other paths that are obviously symmetrical, which enables me to narrow down the search. There are 2 such path first steps:

{1,2,5}
{1,2,3,6}

For both the reasoning is the same: I choose one corner out of 8, one initial direction out of 3, one turn out of 2, and then the next move may produce different paths (different in the sense they cannot be the same after symmetry/rotation).

Therefore any one Hamiltonian path generated by an exhaustive search starting by one of these will give 8*3*2=48 times more Hamiltonian paths.

The first 2 paths starting from an edge (E) are determined (ie constrained) as long as a choice on the way only does not leave out other paths that are obviously symmetrical, which enables me to narrow down the search. There are 2 such path first steps:

{2,5}
{2,5,6}

For the first I choose one edge out of 8, one initial direction out of 2, and then I constrain the first move out of plane x=1 (ie points {2,5,8,11,14,17,..}}) in the x>1 direction (ie points {3,6,9,12,15,18,..}). This is performed using a modified adjacency matrix 'adjMatE'. Then the next move may produce different paths.

For the second, I choose one edge out of 8, one initial direction out of 2, one turn out of 2 and then the next move may produce different paths.

Therefore any one Hamiltonian path generated by an exhaustive search starting by one of these will respectively give 8*3=16 / 8*2*2=32 times more Hamiltonian paths.

The first 3 paths starting from a center of a face (F) are determined (ie constrained) as long as a choice on the way only does not leave out other paths that are obviously symmetrical, which enables me to narrow down the search. There are 3 such path first steps:

{5,6}
{5,14,15}
{5,14,23}

For the first I choose one face out of 6, one initial direction out of 4, and then I constrain the first move out of plane y=1 (ie points {4,5,6,13,14,15,..}}) in the y>1 direction (ie points {7,8,9,16,17,18,..}). This is performed using a modified adjacency matrix 'adjMatF'.Then the next move may produce different paths.

For the second, I choose one face out of 6, one initial direction out of 4, and one turn out of 2, and then the next move may produce different paths.

For the third, it is similar except the choice I want to constrain takes place when the path leaves the plane y=1, which may not take place I choose one edge out of 8, one initial direction out of 2, one turn out of 2 and then the next move may produce different paths.

Therefore any one Hamiltonian path generated by an exhaustive search starting by one of these will give 6*2*2=24 times more Hamiltonian paths.

The path path starting from the center of the cube (M) is determined (ie constrained) as long as a choice on the way only does not leave out other paths that are obviously symmetrical, which enables me to narrow down the search. There is one such path first steps:

{14,15,18,27}

I choose one face out of 6, one first out of 4, one second turn out of 2. Then the next move may produce different paths.

Therefore any one Hamiltonian path generated by an exhaustive search starting by one of these will give 6*4*2=48 times more Hamiltonian paths.

After laying out the plan to compute all the Hamiltonian paths, we intialize the variables and launch the recursive search using the adjacency matrices above.

Te raw results are in the table below.

Note that there is no path starting from an edge (E) or the center of the cube (M).

The raw results of the search are in the table below:

The recursive searchPath procedure in Mathematica is slow, but needs run only once. All the code is available in this github repo.

Each path generated will be given a letter sequence of {E, S,C}, as explained in the introduction.

We compute the sequence of each path and associate it with its vertex list representing a Hamiltonian path.

Note: We must not forget that a snake is undirected, i.e. a letter sequence or the same letter sequence in reverse order is the same snake object. While in our representation, a letter sequence and its reverse are two different sequences. Therefore we transform every snake into its alphabetical order version, by convention.

Then finally we gather the paths by letter sequence. There are 11,487 different snakes. But we still do not know how many different (ignoring rotations/reflections) paths can fold into a 3x3x3 grid graph, as there may be duplicate paths (among the 107,120 counted) for a given letter sequence.

Determination of base paths

In order to determine whether two 3x3x3 grid graphs are identical after rotation or reflection, we must compute all transformations that leave the grid graph, as a whole, unchanged.

A cube can be rotated into itself in 24 distinct ways. Each such rotated cube has 10 symmetrical positions (intial position + 9 axes of symmetry). Finally, as we are looking for undirected graphs, for each of the 24*10=240 transformations thus created, we must check if two solutions are palindromic (identical in reverse order).

The number and nature of the rotations derives obviously from the product: number of faces (6) * number of orientations for one face (4).

The 9 symmetries are represented graphically below.

The 24 rotations, 9(+1) symmetries(+identity), and result in 240 transformations.

Now we define a 'match' function that detects whether 2 paths are identical after transformation, and a function which, for a given letter sequence, keeps only those paths that are not identical after rotation/reflection/inversion.

After this operation we have found all snake cubes, and their solutions.

In order to get an overview of the results, we aggregate the snakes by

number of S in a snake cube
number of solutions (base paths) of a snake cube

and represent them in the table below, where:

the top row is the number of S in a solution snake cube
the left column is the number of base paths for a solution snake cubes
the right column is the total number of solution snake cubes for any S in the letter sequence for given number of base paths
the bottom row is the total number of solution snake cubes with a given number of S in the letter sequence

The table below is the same as the one above except it contains only palindromic snakes, i.e. identical in reverse order.

The tables are available in .csv format

Results

There are 11,487 snake cubes, they have from 1 to 142 solutions, and from 2 to 11 S cubes.

There are 77 palindromic snake cubes, they have from 1 to 45 solutions, and from 2 to 11 S cubes.

There is no snake cube with only C cubes.

The most frequent snake cube has 6 or 7 S and one solution. The same remark applies to palindromic snakes.

The 11,487 snake cubes have a combined number of solutions equal to 51,704, i.e. ~4.5 solutions per snake cube.

The 77 palindromic snake cubes have a combined number of solutions equal to 413 i.e. ~5.4 solutions per snake cube.

But the distribution of the number of snakes as a function to the number of solutions is very concentrated in single digit solutions.

3,658 of the 11,487 snake cubes have unique solutions.

29 of the 77 palindromic snake cubes have unique solutions.

How frequent are snake cubes ? The total number of candidate snake cubes is 2^25/2 = 16,777,216 (each 'cubelet' is either a C or an S, except the 2 ends, and a letter sequence and its reverse are the same snake). The number of plausible candidates snakes (meaning a snake that obviously cannot be folded into a 3x3x3 cube, i.e. a snake with 2 or more consecutive S) is 98,209. Very Few (~0.5%) of all candidatea are plausible snakes, but a decent number (~11.7%) of all plausible snakes are actual snake cubes: Plausible candidates make it quite often.

Below are two CDFs giving access to all snakes and their solutions. They are organized as the the tables above. You must determine the 'Number of S' and 'Number of Solutions' criteria first, and then you can browse through the snakes and their base paths with the 'Snake Cube Index' slider.

The first one displays all the snakes.
The second displays only the palindromic snakes.

You can view it with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.
For the first one, the initialization phase may last ~40s as the CDF imports a large file (Mathematica is slow at importing files).