Python vs. Snake Cube

Christmas Morning

Maybe this has happened to you. You or your kids receive some sort of puzzle from Santa and… well… you’re a smart guy – figure it out, Daddy. The designer of the puzzle didn’t intend for you to just be able to bang the thing back together in 10 minutes. No, you’ll need to struggle for hours, put the thing down several times in frustration and continually adjust your thinking to come up with a _method_ to solve the darned thing.  Meanwhile everyone else is drinking Mimosas and participating in the general merriment of Christmas morning. Sound familiar?

A note for the impatient – scroll down to the bottom of the post to see the animations!

Well that very thing did happen to me this year. It was the infamous 3x3x3 “Snake Cube” (available from fine retailers everywhere).  Very easy to take apart, but… not easy to put back together.  The puzzle is devilishly simple – a 3x3x3 array of 27 wooden blocks all tied tightly together with a hidden elastic string. Each small block is either a “straight-through” piece (elastic emerges on opposite faces) or a “corner” piece (elastic emerges on two adjacent faces.  The goal is to twist the blocks so that the 27 blocks form a cube… again.

After struggling with it for a few hours, I convinced myself that randomly arranging the blocks was going to be a losing strategy. I started thinking of how to construct an algorithm to get to a solution because, well, I’m too lazy to brute force a solution trying random arrangements.  Of course, I wanted to start thinking in Python, wouldn’t you? (Wait, don’t answer that).  Python is soooo fast to just try an idea. Sure I could write something in C++ that might use a class representation to represent each block and it’s position in the cube and it’s orientation, and blah, blah, blah. But the code only has to run once so why spend all that time to build an industrial quality solution. Too much syntax!

Coding Choices

Having decided on Python, I started thinking about how to model the puzzle using Python’s built-in data types.  A tuple (x, y, z) seemed natural for representing the position of a placed block in 3-dimensions. Lists (arrays) are useful for representing the piece types along the elastic string.  The final solution could be a list of tuples that represents the x,y,z position of each block in the sequence. A 3-dimensional list can be used to represent the presence or absence of a block in the cube.

The other major architectural feature I knew I wanted to incorporate was recursion.  Using recursion, I could see the effect of placing each block in every possible legal position.  Recursion allows the code to wander down each and every possible sequence. When an impasse is discovered, the code unwinds and the next valid path is taken.  A solution means that the code was able to place each block in the sequence all the way to the last block using legal moves. That would be represented by a 26 deep stack call stack.

In a situation like this, I usually write a little code, run it, add more detail, run it… What!? I’m not using top-down coding, not writing specifications and requirements!?  Well, this actually *is* top-down coding. I like to write pseudo code in the form of comments with the relevant looping and function calls written in skeleton form. No, the problem is not solved immediately, but the form of the solution is there.  This iterative process gets me into the debug process early so I can have a good solid foundation before the fine details are added.

I like to think of writing a program the same way a sculptor might deal with a block of marble. First, give the block some basic form. Continue by removing smaller and smaller bits of material. Eventually the statue emerges a little at a time. Finally, the fine details are added and the statue is polished.

Coding is pretty much the same: rough out the basic shape (loops, data structures, function calls) , refine the features (encode the algorithms, write the function bodies), refine details (debug and make adjustments for corner cases and unexpected results) and finally buff it out (clean up comments, optimize for speed).

The Solution

Part I – Data Structures

We’ll need some data structures to describe the system. First, we need to describe the pieces in the snake cube chain. I used a simple integer to describe each piece type as follows:

# 1 – straight piece
# 2 – corner piece
chain = [1, 1, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1]

Here’s the declaration for the 3 dimensional array used to show if a block is present or empty:

# block array states
# 0 – empty
# 1-27 the block id in the chain
# the 3x3x3 cube structure used to record if a cell is occupied
sss = [[[0 for x in range(3)] for x in range(3)] for x in range(3)]

And finally, the list to hold the solution:

# sequence maintains an ordered list of tuples representing the XYZ
# coordinates of the blocks as they are placed
sequence = []

Part II – Recursion

We start by placing the first block at position 0,0,0 which I’ll arbitrarily define as the lower left foreground position.

# place the first piece
idx = 1
# start in one corner at location (0, 0, 0)
sss[0][0][0] = chain[idx-1]
sequence.append((0, 0, 0))

Now the fun begins! The one and only function call starts the solution process by attempting to place the next piece.

# get the ball rolling
PlaceNext(idx, sss, last_piece_position, last_piece_entry_face)

I won’t go through the gory details of the PlaceNext() function, but suffice it to say that the function attempts to place the _next_ piece at every possible next location based on the current state of the solution.  Illegal positions outside the boundaries of the cube are discarded. We have to know certain things like the type and orientation of the previous piece to help us discard other illegal positions.

Once we have next piece eliminated positions which impossible, we place the block in the first legal position and call PlaceNext() again. When PlaceNext returns, we know that we have gone as far as we can go with that position and the next legal position (if any) is attempted.

When the idx (also the call depth)  goes to 27, we know we have found a solution and we print it, then return. We’re really just traversing the tree of possible moves to find a leaf at level 27. The recursive function returns whether we have found a solution or not. When the call depth gets back to 1 and there are no more valid, untried positions, we’re done.

Graphical Representation

It was with great fanfare when the program ran correctly that I printed the solution and tried it on the puzzle. It didn’t seem to work! What could be wrong? I discovered that I started to assemble the puzzle from the wrong end – the sequence of blocks is not symmetric about the center block. Direction matters, so I started putting the blocks into position and voila! it worked.

I related the story to my brother-in-law Josh and he said that we had to add some code to visualize the solution process. He suggested vpython based on his experience with the physics textbook Matter and Interactions.

Vpython made it a fairly simple matter to add the code to display the progress of the algorithm. It even has a way to model the blocks with wood grain – niiiiiice. Once we agreed on the Python library we did a bit of pair programming to come up with a visualization that looked good. Of course, we had to slow down the program by adding delays at each call to update the display. The non-delayed, non-graphical version of the code finds all possible solutions for this puzzle in less than a second which wouldn’t be very interesting to watch.

 

See all the actual code here.  Enjoy!