Solving a Snake Cube Puzzle19/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. 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: |
AuthorI work as an actuary and underwriter at a global reinsurer in London. Categories
All
Archives
April 2024
|
Leave a Reply.