For Christmas my girlfriend gave me a series of increasingly difficult wooden-block puzzles, yielding up each one only as I solved the previous. She’d show me the assembled puzzle — to mock me, I assume — then dump it disassembled into my lap1. The first one was a quickly-solved freebie, but the remaining three were pretty difficult. Difficult enough even that I decided to let computers do the boring work and wrote programs to solve them. Ah, the joys of being a software engineer!
And if you think this is “cheating,” I feel the final results from my “bonus round” (at the end of this post) validate the approach.
Round 1 was the King Snake. This puzzle is a 4x4x4 cube composed of 64 linearly connected unit-cubes. The strand of unit-cubes is divided into 46 segments of 2-4 cubes each. Each segment shares a joint cube with its previous segment and freely rotates to form any right angle with that segment. A naive estimation of the problem space is greater than 1e27 (4 right-angles to the power of 46 segments). However, most moves eliminate 25-75% of the remaining problem space by either running into already-filled space or leaving the allowed 4x4x4 grid. Counting on the constraints quickly reducing the problem space, I initially solved this one with a pretty naive depth-first search written in Python.
The Python program took about 5 hours to run, and was designed to find only one solution. But hey! — it worked and found a solution. I later revisited this puzzle with what I learned from solving the others, but I’ll get to that at the end.
Round 2 was the Shipper’s Dilemma Z. This puzzle is a 5x5x5 cube composed of 25 identical, 5-unit-cube, vaguely Z-shaped pieces. For this one I did some research, hoping something about tessellation would help. Alas, even though the pieces are all identical, it appears that this is still an (NP-complete) packing problem. There are 960 positions a piece could occupy within the space, which for 25 pieces yields a naive complexity estimate of greater than 1e492. Ouch. It seemed much less likely in this case that the basic problem constraints would help much, as a naive depth-first search would prune only a few possibilities with each move. I wrote a simple first-try in Python anyway. It got absolutely nowhere, which led me to decide to try something different, something “clever.” And thus down a rabbit-hole I went.
I’ll leave out most of the details, but I wasted a lot of holiday time trying to solve this puzzle with something akin to dynamic programming. I’d build groups of 3 pieces “attached” to a vertex, combine those into groups of 6 pieces attached to a quadrant, combine those into group of 12 attached to a side, then combine those into groups of 24 which (for solutions) would (theoretically) form the full cube with one piece-shaped hole somewhere in the middle. It was a terrible, terrible idea. The computational complexity of each step varied wildly as I changed my methods for forming groups and what assumptions I made about the properties of solution-participating groups. At one point the execution-time was lagging just enough that I re-wrote the solution-grinding code in C. Later the complexity was just where it wasn’t feasible to run at home, but I could run it on Amazon’s Elastic MapReduce. I did learn how to use Hadoop, EC2, and EMR, but — long story short — none of it yielded a solution. I eventually climbed out of the rabbit-hole and went back to a depth-first search, but this time with a much better conceptualization of the problem.
Fast C primitives help3, but the only real way to solve a problem of this sort is by exponentially reducing the search space. The first step is to avoid working on any “unsolvable” states. Many patterns of piece-placement leave gaps which no subsequent piece can fill. I test for this by filling in a copy of the board state with all the pieces which could fit, even if those pieces themselves overlap. If the cube isn’t completely filled, then the initial board state cannot lead to a solution.
Another obvious step for any sort of space-pattern problem is to eliminate all rotations and reflections which result in other states in the same symmetry group. For a cubical puzzle like this one, eliminating symmetries reduces the state-space by a factor of 48. In this case, I did so by initially calculating all symmetrically unique states which have 8 pieces placed, one in each corner. This also has the nice side-effect of splitting the search-space into parallelizable segments, although that turned out to be unnecessary.
The final step necessary to explore all the “interesting” states in a reasonable amount of time is to eliminate the exploration of duplicate states. Just naively iterating over piece combinations will result in trying both piece A then B and piece B then A, even though they result in exploring the same board states. I iterated over a couple approaches to this, but eventually hit upon simply ensuring that each position in the puzzle is filled in a fixed sequence. This minimizes the number of options available for each placement and doesn’t require any explicit book-keeping to short-circuit previously-explored board states.
Final running-time: 2.5 minutes to generate all four solutions.
Round 3 was the RAMU OCTAHEDRON4. This one is kind of a irregular decahedron5 represented as a 5x5x5 cube with the 4 unit-cubes at each vertex removed. It splits into 8 very irregularly-shaped pieces. There are also two small wooden spheres which occupy unfilled space within the cube and “lock” it by preventing motion of the “key” piece unless the spheres are shifted into particular positions. The site calls the Ramu Octahedron their “most difficult puzzle” and claims that only one person has solved it without reference to the solution. The difficulties of this puzzle are three-fold: the irregularity of the pieces makes conceptualizing their spatial placement difficult; many of the pieces can only be placed by combinations of separate “insertion” then “locking” motions; and once the puzzle is assembled, one must determine how to maneuver the spheres within the unfilled internal space to allow re-disassembly.
Fortunately the piece-irregularity holds little difficulty for a computer. After laboriously entering the shapes of each piece, I was able to re-use code I’d written for the previous puzzle to generate all the interesting piece rotations and translations6 and their various combinations. Once that gave me the solution spatial arrangement, it required a bit of trial-and-error to figure out a working piece order and insert/lock sequences, but I was able to manage it by hand. Figuring out the necessary unlocking rotations was also easy enough, at least after I added a map of the unfilled internal space to the solution.
Final running-time: 1 second to generate the single solution.
Bonus round, back to the King Snake. I decided to come back to this puzzle with what I’d learned from solving the others and try to generate all its solutions in a reasonable amount of time. I didn’t have any new ideas about how to frame the puzzle, but I did have some new implementation tools: pre-generating and indexing by position all legal piece arrangements, and representing puzzle states as bit-fields. These two together allow for a blazing-fast solution.
Final running-time: 30 seconds to generate all four solutions7.
If you own this puzzle, you may at this point be thinking “Wait, what?” The marketing copy and provided instructions for the King Snake claim there are only two solutions. But nope, four. The two extras solutions are very similar to each other, but are quite distinct from the two “official” solutions, and none are simply symmetries of the others.
“Cheating” — hah!
Puzzle-solving code available for your edification.
1 Best Christmas present ever, seriously.
2 For comparison, chess apparently has between 1e43 and 1e50 legal board states.
3 Most actions on a the puzzle-state are just a few bitwise operations.
4 Which I really like putting in all caps, for some reason.
5 Yeah, the name confuses me too.
6 But not reflections, what with three dimensional limitation and all.
7 FYI, I number from the opposite end than the provided solutions.