Solving a Snake Cube Puzzle

My colleague at work gave me a snake cube puzzle to try to solve, and if you haven't tried, they are a lot harder to solve than they look.

After trying and failing for about 10 minutes to solve the puzzle, I had a great idea, why not waste a couple of hours writing a program to solve it for me? And then a couple of hours turned into a couple more hours, but I got there in the end!

The aim is to wrap the snake into a 3x3x3 cube. Here is what the snake puzzle looks like when it is unwrapped.

How does the Program work?

There are two main approaches to solving the puzzle programmatically, you could either systematically enumerate all permutations of the snake, or randomly try different permutations until you find one that works.

I went with the second option. which seemed like it would probably be computationally slower, but easier to program.

I decided to write the code in Python, it works by randomly twisting the snake one joint at a time, and restarting everytime the snake either crosses itself or goes outside a 3x3x3 grid.

The code runs 100,000 simulations in approximately 20 seconds on my laptop, which turns out to be just about fast enough to get an answer when you leave the program to run for a couple of hours.

The code:

from random import randint
import time

def f(x):
    return {
        1: 1,
        2: 2,
        11: 0,
        12: 2,
        21: 0,
        22: 1,
    }[x]

def drandomu():
    drandomint = randint(1, 2)
    if drandomint == 1:
        drandomint = -1
    else:
        drandomint = 1
    return drandomint

def drandom(iDirection):
    drandomint1 = f(iDirection * 10 + randint(1, 2))
    return drandomint1

CurrentTime = time.clock()
vArray = [[[0 for x1 in range(3)] for y1 in range(3)] for z1 in range(3)]
vMaxArray = [[[0 for x2 in range(3)] for y2 in range(3)] for z2 in range(3)]


iMax = 0
iTotalBlock = 1
vChain = [3, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2]
m = 1000000
limit = int(m * 1)
for lSim in range(limit):
    try:
        GiveUp = "False"
        iDirection = 0
        iTotalBlock = 1
        vCurrent = [0, 0, 0]
        for x in range(3):
            for y in range(3):
                for z in range(3):
                    vArray[x][y][z] = 0
        for iLink in range(17):
            if GiveUp == "False":
                if iLink == 0:
                    for iBlock in range(vChain[iLink]):
                        if iBlock > 0:
                            vCurrent[0] += 1
                        vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] = iTotalBlock
                        iTotalBlock += 1
                else:
                    iDirection = drandom(iDirection)
                    iUpOrDown = drandomu()
                    for iBlock in range(vChain[iLink]):
                        if vCurrent[iDirection] == 0:
                            iUpOrDown = 1
                        vCurrent[iDirection] += iUpOrDown
                        if vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] != 0:
                            if iMax < iTotalBlock:
                                iMax = iTotalBlock
                                for x in range(3):
                                    for y in range(3):
                                        for z in range(3):
                                            vMaxArray[x][y][z] = vArray[x][y][z]
                            GiveUp = "True1"
                            break
                        else:
                            vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] = iTotalBlock
                            iTotalBlock += 1

        iTotalBlock = 0
        for x in range(3):
            for y in range(3):
                for z in range(3):
                    iTotalBlock += vArray[x][y][z]

        if iTotalBlock == 378:
            print(vArray)
    except:
        pass

print(int(time.clock() - CurrentTime), "Seconds")
print(int((time.clock() - CurrentTime)/60), "Minutes")

for x in range(3):
    print(vMaxArray[x])

print(iMax)
 

The Solution

The program eventually gave me the following layout as a solution:

[[1, 16, 23],    [18, 17, 22],    [19, 20, 21]]
[[2, 15, 24],    [5,  6,    7],     [10, 9,   8]]
[[3, 14, 25],    [4, 13,  26],    [11, 12,  27]]

The easiest way to think about the solution the program gives is to think of the three blocks of three digits on the left as the bottom layer, the second block of three digits as the second layer, and then the third block of three as the third layer. So the 4th block is directly abov the third block.

Here is the completed puzzle: