Thursday, May 5, 2011

Snaky Cube

The following is a puzzle that I’ve encountered at the Kubiot (Cubes) restaurant in Tel-Aviv.
The target of the puzzle is to make a 4x4x4 cube out of this snake like shape. The small cubes are connected to each other with a cord so it’s only possible to rotate them, but not to change their position. This puzzle is a larger version of a similar puzzle that makes a 3x3x3 cube.

 Where the target is to get to this:

The guy at the restaurant said that he would give a free meal to anyone who solves it on the spot. Don’t be fooled by the 3x3x3 version of the puzzle, this one is a hard task indeed, given the fact that for a guy who knew the solution beforehand, it took about 15 minuets to set it right. So I decided to go “pirate” on this one, and take the picture that you saw at the top.
My mile stones are:
  1. Writing a script to solve it at home.
  2. Memorizing the solution.
  3. Collecting my ~10$ prize.
 1. Brute-forcing to solution.
Python to the rescue.
I entered all the information about the puzzle has lengths of straight lines that could not be rotated.:
data = [3,1,2,1,1,3,1,2,1,2,1,2,1,1,1,1,1,1,1,1,2,2,1,1,1,1,1,2,3,1,1,1,3,1,2,1,1,1,1,1,1,1,1,1,3,1]
My approach is to build a 4x4x4 array of zeros and try to fill it with squares. I defined a Point3D class for the millionth time. And set-up the cube.
Two small questions that came up during the writing:
1. Does anyone know about a simple implementation of Point3D in Python, so I won’t have to write it again.
2. Does anyone know about a simpler way to define the 4x4x4 cube other then:

cube = []
for x in xrange(4):
    ll = []
    for y in xrange(4):
        l = []
        for z in xrange(4):

Now I define all the valid moves in the puzzle, and include recursively the next valid moves, as it depends on the last move.

XDirectionP = (Point3D( 1,  0,  0), [])
XDirectionM = (Point3D(-1,  0,  0), [])
YDirectionP = (Point3D( 0,  1,  0), [])


The main recursion is as following:

def nextMove(pos, dataLeft, currentDirections):
    global cube
    global highestLevel

    if 0 == len(dataLeft):
        return True
    length = dataLeft[0]
    for move in currentDirections:
       newPos = pos + (move[0] * length)
       if isValidLocation(newPos):
           if tryToSetCubes(pos, move[0], length, len(dataLeft)):
               if nextMove(newPos, dataLeft[1:], move[1]):
                   return True
               clearCubes(pos, move[0], length)
    return False

Apparently this solution, is good enough it took %d seconds to solve it, no extra improvements were required... That’s sad, I kinda’ hoped for something more advanced.

I’ve translated the result into a string of first letters of the valid moves (Left, Right, Up, Down, In, Out), just to get the 46 letters string “RULODRIULOLILURORIRODLOLUIUODIROUIRDODILDROLUR”.
Next I called my good friend Werner, to manifest a sentence out of the string so it would be easier to memorize. The genius came up with the following:
“Recently, upon learning of dental recovery, Ian Underwood laughed out loud. In laughing, underwood remarked, optimal recovery is realized. ordinarily, during laughing out loud, universal imagery unfolds. Or does it? Regardless of universal imagery, rarely do old dying imbeciles laugh. Don't ruin our laughter, Underwood remarked.”

Here I returned to the restaurant with two of my good friends who helped me with acting like I’m going trail n’ error to solution, and it’s doing very well, but have no clue of what am I doing. On setting the very last move to the solution, a crack sound has echoed the place, leaving me with a baffled look at what had happened.

Alas!!!, I shouted out loud, realizing that not only am I not going to get a free meal, but I will probably have to buy them a new puzzle. Fortunately, they told me not to worry, and that it happens all the time, they would replace the cord by next week, so I could try again then.

Now three weeks later and they still didn’t fix it! I started to look-up this puzzle to check where they bought it, and I found the following web site:
Or more specifically: