36 Cube

So I’ve been geeking out over a puzzle that I got for Christmas this year. The puzzle is called 36 Cube. If you have this puzzle, and haven’t solved this cube, or would like to in the future, or have any other reservations about reading spoilers,

PLEASE STOP READING.

This is not a hints post, and I do not ease you into a solution slowly. This is a post about how I solved the puzzle and some interesting facts about the puzzle I found out afterwards when I began to dive deeper into the solution set. As well as the programming that went with it.

If you would like some proper hand-holding, please see How to solve the 36 Cube puzzle – hints & solution for hints (and samples of the program that got me started down my path).

AGAIN, IF YOU DON’T WANT SPOILERS, PLEASE STOP READING!

Apparently you either don’t care, or have already solved the puzzle…

So when I first got this puzzle, it seemed moderately easy, contrary to the warning on the box. My brother was actually the one to take the first whack at it, and he did pretty well, getting 34 of the 36 pieces on the puzzle, but those last two were giving him issues and he was unable to solve the puzzle before he had to leave. Later that night, I took my first stab at it, and also got 34 of the 36, and after an hour or so of fiddling, and trying to brute force my way into a solution, I looked it up online. Not for a solution, but for more information on the puzzle and what kind of math was involved in solving it, so I could give it a more educated attempt. After reading the wiki page on Graeco-Latin squares, I noticed that Euler had conjectured that there was actually no solution to the order 6 square (of which this puzzle is).

This blew my mind. I could not understand how there could be a puzzle with a solution to which there was (now) mathematical proof that there was no solution. I thought either the proof was wrong (highly unlikely), the inventor had found a solution to the age old problem (also not likely), or the wiki page was wrong (more likely, but still not very). I then found other wiki pages relating to the puzzle where the inventor said about the order 6 problem, “It struck me as the basis for a potentially great 3-D puzzle, and what eventually became 36 Cube.” And this is when I became suspicious of the puzzle.

I remembered that when I was initially inspecting the puzzle, I had noted that some of the bases were not the same, even when the base was for the same height piece. I thought this was odd, but thought nothing more of it, chalking it up to manufacturing issues. After become suspicious, I went back to the puzzle and inspected it further. It occurred to me that there might be some chicanery going on, so I placed a few of the smaller, more innocuous-looking pieces on the board (to have a height measuring stick of sorts) and proceeded to try the height 6 pieces on all of the larger piece bases, including the height 5 bases. And lo and behold, when I placed a particular piece of height 6 on a particular base of height 5, it fit. I also tried the height 5 pieces on all of the height 6 bases, and one of them fit as well. This is the trick to the puzzle. Instead of solving the impossible, the inventor modified the puzzle to allow it to “cheat” it’s way to a solution. Once I had the first few trick pieces in place, it was simply a matter of logic to solve the rest, and I had the solution within the hour.

But I couldn’t stop there. I wanted to know how many actual solutions there were to the puzzle, so I sat down with a few example programs and began to pound out my own program to solve the puzzle.

My Program (some functions ported from script written by Daniel Hepper, who wrote the hints post above)
(Full unedited script)

It’s not the most elegant program around, nor does it use the most elegant algorithm, but it works, and it works fairly well. I started out by trying to solve a single color for each row [function solve_color( )], but I soon figured out that this would be difficult to make work for finding all solutions, so I abandoned it. I then wrote a function to iteratively solve each piece size in succession, finding all possible locations for that size, and then iterating further along each solution path until all the pieces were placed, or it failed for whatever reason [function solve_color_by_pieces( )]. If it succeeded in finding a solution, I tacked the solution array on the end, and continued down the next path. If it failed, I deleted the current solution path and continued on with the next one.

When I first ran the function, solving for yellow (which has one of the “trick” pieces), it gave me two solutions. Both of which I had manually proven earlier, which is a good sign for the program. I then added orange into the solution (the other “trick” piece), and it gave me one orange solution for each of the yellow solutions. The odd thing is, both of the yellow-orange solution sets have the same footprint. What this means is, I only have to continue solving for one of the two yellow-orange solutions, and they will both work. I just multiply the total number of solutions I end up with by two, and I have my grand total of solutions.

As I continued, I first tried solving for the whole puzzle, just to see what came out. What came out was an “out of memory” error (I told you it wasn’t the most elegant). Apparently my program could do with some optimizing. I increased the allowed memory to 2GB(!), and ran it again. I again got the “out of memory” error.

Wow.

Ok, looks like I need to do this with some manual intervention. So I ran it with just the red color. And it quickly spit out 8 solutions. I added those constraints to the initialization one by one, and ran it again for each, this time solving for green (the colors are arbitrary). It came up with 3 solutions for each of the 8 red solutions for a total of 24 solutions so far. As I was looking at the solutions, I noticed that a lot of them were the same, so I threw them in a lump and sorted them. As I was going through the sorted list, I noticed that there were 3 duplicates of each green solution, which brings my unique green solutions down to 8. I also noticed that there were similarities between the 8 red solutions and the 8 green solutions, so I threw them all in lump again, and sorted that group, and guess what… they were all the same. Each red solution was repeated in the unique green solutions. This struck me as odd when I saw it, but now that I think about it, it makes sense. They are the same solutions, they just move around each other.

This pattern continued with the remaining two colors (blue and purple), blue had 2 solutions for each of the 8 unique red-green solutions, but only 8 of them were unique, and they were the same 8 as the previous red and green. And purple only had one solution for each of the 8 red-green-blue solutions (which makes sense, since it’s the final color and really only has one place to go), and again, they were the same 8 patterns. But when I looked at the final 8 solutions, I noticed that they had similarities within them, so I labeled each of the 8 solutions, and put them together, and it basically ended up being 2 unique solutions, with various permutations and color switching for the others.

So with my final 2 solutions, multiplied by my initial 2 yellow-orange solutions, that’s a grand total of 4 solutions.

I don’t know why, but I assumed that a puzzle of this size would have more than just 4 unique solutions. But I guess that’s part of the game, false assumptions and trickery.

UPDATE: After feeling like my program was incomplete due to it’s inelegance and inability to calculate a complete solution, I went back to it, and tweaked it a bit to get it to properly calculate all the valid solutions.

I finally got it to output all the solutions after initializing it with one of the yellow-orange solutions. It cranked for a couple of minutes, and spit out 48 solutions. I knew that these 48 solutions were just the various color switching permutations of the unique 2 solutions, but I really wanted the program to crank out those unique 4 solutions, and nothing more. So I added the bare minimum of initial parameters (the two “trick” pieces) and set it up so that after the program found each solution, I converted it to an unambiguous state and compared it with any previous solution, and if that solution had already been found, it disposed of that solution and continued on. What I got at the end after the program cranked for a couple of minutes were 4 unique solutions. This not only made me pleased with my program, but pleased with my previous manual calculations.

And just to clean things up, I removed all of the debugging output from the program, and guess what… the program cranked out all 4 solutions in less than a second.

Wow. My program went from taking over 5 minutes to throw an “out of memory” error, to calculating all 4 unique solutions in under a second. I was actually pretty shocked about that, and pleased at the same time.

So I give you the 4 unique solutions:

1. B O G Y P R
   R G Y P O B
   G R P O B Y
   P B O R Y G
   O Y R B G P
   Y P B G R O
2. B Y G O P R
   R G Y P O B
   G R P Y B O
   P B O R Y G
   Y O R B G P
   O P B G R Y
3. B O P Y G R
   P B Y R O G
   G R B O P Y
   R G O P Y B
   O Y G B R P
   Y P R G B O
4. B Y P O G R
   P B Y R O G
   G R B Y P O
   R G O P Y B
   Y O G B R P
   O P R G B Y

Here is my updated and optimized program:
https://pastebin.com/KiJMjzTa

That is all, I’m happy with this program and the solutions it calculated and (probably) won’t be messing with it anymore.