THE REINSURANCE ACTUARY
  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer

Solving a Snake Cube Puzzle

19/12/2016

 
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.
Picture

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:
Picture



Leave a Reply.

    Author

    ​​I work as a pricing actuary at a reinsurer in London.

    I mainly write about Maths, Finance, and Technology.
    ​
    If you would like to get in touch, then feel free to send me an email at:
    ​LewisWalshActuary@gmail.com

    Categories

    All
    Actuarial Career
    Actuarial Exams
    Actuarial Modelling
    Bitcoin/Blockchain
    Book Reviews
    Economics
    Finance
    Fun
    Insurance
    Law
    Machine Learning
    Maths
    Modelling
    Physics/Chemistry
    Poker
    Puzzles/Problems
    R
    Statistics
    Technology
    VBA
    Web Scraping

    Archives

    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    May 2020
    March 2020
    February 2020
    January 2020
    December 2019
    November 2019
    October 2019
    September 2019
    April 2019
    March 2019
    August 2018
    July 2018
    June 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    April 2016
    January 2016

    RSS Feed

  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer