The Eternity II Puzzle is a 256 piece edge-matching puzzle. To solve the puzzle, you must lie out all 256 tiles onto a 16×16 grid with all the edges matching. A single seed tile is positioned in the middle of the board. Tomy UK Ltd. released Eternity II in 2007 with a $2,000,000 prize for solving it. The designers tried to generate the hardest to solve puzzle with this specification. I picked up a copy in 2008 and did some work trying to solve it back then, but dropped it as other priorities came up.
Back when I was working on this initially there were a variety of people trying to solve it with stateless DFS, or randomly positioning all tiles and trying to shuffle the board to maximize the number of edges that matched. I tried a variety of these solutions and some of my own invention. One method I tried was a construction solution where I build all possible sets of two tiles, combined those to all possible sets of four, etc, resulting in storing all combinations of these sizes: 2×1, 2×2, 4×2, 4×4, 8×4, 8×8, 16×8, 16×16. The idea was after only eight steps I could solve the whole board. That rapidly proved a bad idea as the number of valid combinations at just the lower stages were so numerous they dwarfed my storage capacity. I had little hope of things improving in the higher stages. I ran a simulation running a DFS to generate possible 8×8 squares and counting (without storage) and got to the hundreds of millions before I stopped. There was simply too much data generated for me to store. To make matters worse, I knew a vast majority of these solutions weren’t conducive to the actual solution, as this approach ignored the seed tile. So I didn’t want to store a bunch of data that wasn’t useful in generating a solution. That wouldn’t get us anywhere.
A number of things have changed since 2009. In 2010 they ended the prize portion of the puzzle, and they’ve shut everything about it down. However, there are a number of positive developments for this puzzle. For instance, the price of storage has fallen dramatically. I could conceivably store all those 8×8 squares if I wanted, I would have the capacity for it (not that I want to waste space that way). Computing power is also easier to come by. In 2009 I had a desktop and a laptop, now I own a small cluster of compute power at my disposal, and can easily expand that compute power with the cloud. I’ve also grown as a developer and have more experience with distributed solutions. Given all of this, I will tackle this problem again. I don’t know if I’ll actually solve it, the solution space is enormous, and my solution may never stumble upon the answer. But I still think it will be a fun way to learn more about distributed systems, and there are several interesting problems that I can tackle within this context.
It should be fun.