For Christmas one of my friends presented me with a block puzzle. This puzzle was basically a Rubik's Cube, but the difference was, instead of having colours on each side, all the sides were coloured yellow. Instead, a snake, with two heads, starts at the centre of one of the faces of the cubies and snakes around the other cubies to its endpoint. Once scrambled, the idea is to unscramble the cube so that the snake forms one continuous curve.

Attempt 1: solving legitimately

This proved to be extremely difficult. To begin with, I am very bad at the Rubik's Cube puzzle, so simply rearranging the cubies using ordinary legal turns is not something I can do. I was restricted to trial and error.

Attempt 2: take the cube apart and solve by eye

The next problem was that even having taken the cube apart - and unfortunately I broke one of the pieces in order to do this, but the puzzle itself was still intact enough to be entirely solvable, so no worries - you still don't know what the solution is. You have to actually figure out the snake's path before you can implement it, and that is not at all obvious. I believe the original puzzle may have come with a solution guide, but mine certainly didn't!

Attempt 3: take the cube apart and solve on paper

The next problem is that finding that solution is very, very difficult to do by hand. I divided up all of the cubies and took a note of the face configuration of each one and spent a great deal of time matching the various connectors together, hoping to show that there were restrictions on how certain pieces could be placed, which reduced the possibility space. No such luck. As later work showed, there are very few restrictions on how the first few cubies may be placed in the cube. The only trouble usually arises after 20 or more of the 26 cubies have been placed. You can't account for that early on.

Attempt 4: take the cube apart and solve by computer

That meant that my last option was brute force. So I sat down and spent a few days writing a Perl script to solve the problem for me. This in turn was very difficult. The script works like this:

1: Cube Space

The space of the cube was divided up into a discrete three-dimensional 9x9x9 grid of points, from -4 to 4, centred on (0, 0, 0). Thus, each cubie occupies a 3x3x3 volume of points, and adjoins several other cubies. Each grid point has a value of a single-character string, depending on what is currently occupying that point in space.

2: Cube Types

There is a list of four types of cubie. Centre, Face, Edge and Vertex. The centre cubie is always hidden and has no "pattern" upon it. A Face cubie only exposes one of its six faces, and this face can be rotated. An Edge cubie exposes two faces, and a Vertex cubie exposes three faces.

Each type of cubie has a "canonical location", a set of coordinates marking the centre where it is located. These are (0, 0, 0), (0, 0, 3), (3, 0, 3) and (3, 3, 3) respectively.

3: Cubie Data

Next we have a set of data laying out the face configuration of all the cubies in the cube. These configurations give the coordinates of each piece of snake which occupies part of the cubie - assuming that the cubie is at its canonical location and orientation.

4: Rotations

We also have three routines which can rotate a point around the X, Y or Z axes in three-dimensional space. By repeatedly applying these routines, it is possible to take the single canonical location and orientation of a cubie, and generate all the possible locations and orientations of a cubie. Note that for the Centre cubie, there are no alternate possibilities, whereas for a Face cubie there are 4x6 = 24, for an Edge cubie there are 2x12 = 24, and for a Vertex cubie there are 3x8 = 24. This discounts the odd duplicate in the case of a few symmetrical cubies.

5: Commit and Uncommit

Next, we need a procedure to "commit" a cubie into the cube, and another procedure to "uncommit" the cubie if it turns out that this was a wrong move.

6: Consistency

We need a procedure which can check whether the current configuration of the cube is "consistent" or not. If a cubie adjoins an empty space, that's fine, because we don't know what will be placed there. But if two cubies adjoin, then we must make sure that the combination of snake and non-snake on one side of the join matches the combination on the other side of the join, i.e. that this is a good connector.

7: Recursive Solver

The final piece of the program is the recursive routine. This routine takes the "current" configuration of cubies, including a list of the cubies which have already been inserted into the cube, and then systematically tries to insert another cubie, then call itself. The procedure is recursive, so that when it reaches depth 27, all 27 cubies have been placed, and the execution terminates. On the other hand, if it turns out that the current situation is unsolvable (i.e. all situations arising from this one are inconsistent), then the cube is unsolvable and the effort terminates.

8: Display

Oh, and we also need a routine to output the solution to the screen. That's kind of incidental but it was one of the first things I wrote so that I could keep track of what I was doing.

So did it work?

This is a classic example of a program which doesn't have to be perfect, it just has to be "good enough". My first attempt at the program is snakecube.pl. It's not 100% efficient and does rather more calculation than it might need to do in order to check for validity. It also lacks comments and portability. Still it tests more than 1000 cube configurations per second, outputting every 1000th attempt to the screen so that I could follow its progress. After some preliminary testing I decided that the program was likely to run for a long period of time, so I set it to run overnight. If it wasn't solved within a day or two, I'd consider terminating the process and trying to optimise a little.

However, here's the solution that I found when I got up the following morning (total running time probably something like 9 hours 45 minutes):

And here are some photos of the solved Snake Cube:

Update

Some fairly obvious tweaks for optimisation (like not checking the ENTIRE cube for consistency every time a single cubie is inserted) resulted in snakecube2.pl which finds its first solution in a matter of seconds and goes on to find thousands more within minutes. Evidently solutions of the cube are quite dense on the ground, even if it takes a great deal of processing power to find them. I can't be bothered to take the next logical step, which would be to chart exactly how far my script progresses through the possibility space of all cube configurations - of which there are, using this algorithm, 8!*3⁸*12!*2¹²*6!*4⁶ = 1,530,664,174,762,362,289,520,640,000 - and thereby evaluate just how many solutions there are likely to be and how difficult it is objectively to find one just by rearranging pieces at random.

Another interesting note is that many solutions, as I'd suspected from the beginning, involve the creation of a closed loop as well as the single snake.