## Chess Board Snake Cube

I had made some puzzles that were predesigned, that is, someone else had already made the arrangement, but with a bit of personal flair. For example, a soma cube with Rubik’s coloring and the modular origami bedlam cube. After making a pentomino chess board and a 3x3x3 snake cube out of paper pulp, I was looking for another puzzle to build. (Here are some other projects I’ve made)

I thought about the 4x4x4 snake cube and quickly realized that the 64 cubelets could potentially also make an 8×8 square.

I searched online for anyone who had done it. Finding no one, I set my mind to finding a way or finding that it was impossible.

*****************************************************************************

How could I figure out a snake arrangement that could form a square *and* a cube?

*****************************************************************************

**Huge Possibilities**

Calculating the number of different snakes from 64 cubelets was easy enough. There are 3 kinds of cubelets: the ends, the straights, and the turns. There are 2 ends and then each of the 62 remaining could be straight or turn, giving 2^62 (or 4,611,686,018,427,387,904, over four quintillion) different 64-cubelet snakes. Of course most of them wouldn’t make a square or a cube, let alone both. With some research I found that a 4x4x4 had 27,747,833,510,015,886 possible Hamiltonian paths. This counts rotations and reflections as unique, which was not of concern to me, so I was only looking at about one quadrillion possibilities. As for squares, I only had to look through 3,023,313,284 (really only about 378 million discounting rotations and reflections). Once I discovered these numbers, I knew a few things.

I was going to need to write a computer program (and I’m no programmer). I should start with finding paths on the square (it’s the smallest big number). If there wasn’t any overlapping solution, it would be incredible (maybe there’d be an article to write on that).

As with most work, the write-up makes things sound a lot smoother and more orderly than they really were. There was massive ~~wasted effort~~ exploration coming to the conclusions I did. It required a lot of learning split up over a long time (I’m getting a PhD in education policy, not snake cubes).

It ended up being possible to find a snake arrangement that produced a cube & square. However, in my pursuit to built the first one I found I left unfinished another aspect of the search I would love to figure out: how many solutions are there? I would love to have a complete map of all the snakes that solve both ways and all the different ways each snake solves. It is possible that one snake arrangement might have, for example, four cube solutions (ignoring rotation/reflection) and ten square solutions while another snake has unique solutions for both. Of course, with the carving out I’ll discuss later, another layer of matching is introduced that would make multiple solutions unlikely. But for snake cubes themselves it would be interesting to list the snakes by solutions spaces.

I would also be interested to see what percentage of hamiltonian paths for the 8×8 and 4x4x4 make it onto the list. Based on my work so far, I’d say it’s a small percent.

**8×8 Hamiltonian Path Creation**

So I wanted to find hamiltonian paths for the square. But with billions to work with, how was I to search all paths without missing, repeating, or wasting time?

Here’s a video of the algorithm that I finally landed on for finding hamiltonian paths on the 8×8: (I’m kind of a slow talker, so you might want to watch at 1.5 or 2x)

Basically it adds a square at a time by

Finding the neighbors of the end of the path

removing any options that obviously don’t work

and stepping back when no options exist.

It is a depth-first search, trying to find the longest path before moving to the next.

You can also watch this video for a walkthrough of my code.

**Snake Creation**

The algorithm made the snakes alongside the square paths. Sometimes different paths used the same snakes.

**Cube Checking**

After finding a bunch of paths on the 8×8, I needed to see if any of the snakes formed by those paths could also make 4x4x4 cubes. I suppose I could have made the program run each 8×8 as it came along but I didn’t, perhaps the batching saved some computation because I removed repeated snakes (those with different paths but same snake configuration).

Basically it functions much like the 8×8 builder but selects the options based on the cubelet type. It starts with the first snake and the first position. It tries all the options, tracking any full paths produced. Then it proceeds to the next position and so on. Then proceeds to the next snake.

**Finding the One**

After making a whole bunch of 8×8 paths, I grabbed a few and eventually found a snake that fit the criteria. I double checked it to make sure it worked. Below is one solution in each form (I’m not sure if there are others for this particular snake)

Snake: 3, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 3

**Chess Board**

It is very common for snake cubes to utilize a checkered pattern. Here I had a snake cube that could form a chess board in its 8×8 form. I thought it would be especially awesome if in its cube form all the chess pieces would fit inside. For this to be worth it to me, I needed the pieces to be appropriately sized relative the board squares and I needed all the faces showing on the cubelets in both forms to be smooth.

Eventually I came up with an arrangement that seems to work. I learned 123D Design so I could construct a virtual prototype and I’m now working on a physical one. After a rough draft I may have to produce a high-quality one.

This relatively simple idea became a consuming project that led me into learning from several fields.

Here’s my code

Here’s my design