■ Snake cube puzzle "AI" solver

The brainier folk among you must have come across the snake cube puzzle, usually a string of wooden cubes strung together, that must be twisted and turned to form a 3x3 bigger cube as such:

Watching the video it seems all too easy, but I assure you it's a big headache to figure it out. There are more than one possible folding configurations anyway, so let's refer the whole problem to our trusty computer's CPU to solve it for us. The solution algorithm is straightforward as long as you get your head around the 3-dimensional nature of the problem

The above figure shows a small snake made of 9 cubicles, all laid flat on a table. There are 5 arms connected by 4 elbows. One needs to focus on the elbow cubicles like number 3 above, where there's a change of direction. Each elbow can turn in 4 possible ways (angles), left/right or up/down. This simple snake has 4 elbow joints, so the total possible arrangements are 4*4*4*4 = 256 (degrees of freedom). The alternatives quickly multiply in longer snakes as each extra elbow adds 4 new possible twists, exponentially. For example, the video example has 16 elbow joints, and the possible arrangements are 4^16 = 4,294,967,296 — which explains why these little puzzles are so hard to solve!

A simple approach to solve this kind of puzzle is to try out all the possible angle turns, one by one, as one would try to hack a numeric combination lock trying out each and every number until the magic combination is struck. This is called brute force enumeration approach. For the snake puzzle, we have more than 4 billion alternatives to consider, which would rule out brute forcing as impractical. Luckily though, most elbow turns are clearly infeasible, so only a small fraction of the turns need be considered. An elbow turn is infeasible if it violates any of the following rules:

Any edge/side of the partially solved cube is longer than 3 cubicles (it can never fold into a 3x3x3 big cube)
The attempted arm turn clashes with previously folded cubicles (i.e. you cannot turn an arm if there's no free space to complete the turn)

Once we encounter an impossible turn, we can ignore all the remaining elbows, so the savings really add up, and brute force enumeration can succeed — although not quite "artificial intelligence" (what is AI anyway?).

Click to download snake puzzle solver (7 KB)

Source code in Matlab, but you could easily translate it in Python or whatnot

The matlab source code is pretty straightforward, if you exclude some headaches regarding the 3-dimensional arrangement of the arms and cubicles. There are many snake configurations (both symmetric or asymmetric), and I suppose the code can solve all of them, if you define the elbow cubicle locations in the array elbows. For instance, the snake on the video above is represented as:

elbows = [3 5 7 9 10 11 12 14 16 17 18 20 21 23 24 25];

where each elbow cubicle number is laid out in increasing order (e.g. we have elbows at cubicles 3, 5, 7 and so on).

The solver is using recursion, starting from the first elbow and adding extra turns till an infeasibility (or a solution) is found. The 4 possible turns at each elbow change the direction of the subsequent arm in a clock-like fashion, as in the picture to the right. So first we try 12 o'clock (turn up), then 3 o'clock (right) and so on. These turns are relative to the current orientation of the arm considered.

There are multiple ways to solve such snakes (e.g. 8 possible folds for our test snake). Some folds are easier than others. As we don't have a nice GUI to show the solution, we must interpret somehow the program output. Working with clock turns is rather confusing, so instead the program shows the orientation of each arm in XYZ space. The positive X and Z directions (black) are on the paper and the positive Y goes inside the page (to the back). Negative directions are shown in red.

For our test snake, this is the first solution found:

xyz arm orientation:
1:X+ 2:Z+ 3:X- 4:Y+ 5:X+ 6:Y- 7:X+ 8:Z- 9:X- 10:Y+
11:Z+ 12:Y- 13:X+ 14:Y+ 15:Z- 16:X+ 17:Z+

This means we put the first arm in the X+ direction (to the right), the second goes up (Z+) and so on (see the first 3 arms to the right).

For asymmetric snakes, arm numbers follow the declaration of the elbows. You can try folding in reverse direction if the forward solution is harder