How to Win $2 Million Dollars

Its simple, just be the first to complete this 256 piece puzzle before the end of next year. Easy, right? Looks can be deceiving!

I have been interested in this line of puzzles ever since I received Eternity I for Christmas way back in 1999. It presented a fun programming problem to me, and I enjoyed tackling the various methods of programmatically solving it. When the puzzle was solved (by two mathematicians) I kept an eye out for news of a second puzzle.

And then I found that news, at the beginning of this year. There were some details on the format of the puzzle (i.e. square pieces, 8x8 board) out there... enough to get me a head start on a solver for this puzzle. I found my old eternity newsgroup, now resurrected as a place to discuss the new puzzle. Discussions were already taking place, a lot of which were based on expected number of solutions, piece tileablity, things that were very important to the previous puzzle. I completed my solver and anxiously awaited the release.

I had my puzzle and the two hint puzzles shipped to me from England. My wife started solving the two hint puzzles by hand while I encoded the 256 pieces of the main puzzle into a file. How deceivingly simple the two clue puzzles were... she had them both solved in less than an hour. And this was about how long it took me to finish encoding. I let loose my solver (an instance on each of my computers) and watched it. It really was fascinating to watch... it would place a bunch of pieces... remove some... place some again... really neat stuff. As a programmer, I really enjoy seeing things I have spent long hours on work the way they should. I had really high hopes.

But alas, this puzzle is a lot more difficult... the search space is simply to vast. My best "partial" solution to date was discovered last weekend. A 216 piece partial, the silhouette of which can be seen here. I cannot show the actual picture due to copyright issues. Unfortunately my first generation of solver did not save off partial solutions... I'll never know if I had had something better in the past.

My first generation solver placed tiles one at a time. Last month I finalized my second generation solver (running now) that places tiles via a 2x2 "super" tile. I pre-create all the 2x2 tile combinations when the solver starts up, so my puzzle is effectively an 8x8 board but with millions of pieces. My third generation solver will handle 2x4 tiles... sort of. I did some math and if I wanted to pre-create all the 2x4 "super" tiles ahead of time I would need something like 20 terra bytes of storage to save them all!

So I decided to do something a bit different here and only generate the top and bottom edge "super" tiles for only around 25 gigs of storage. Since the storage requirements are large, I will need to save them to disk instead of to memory. This will reduce the speed of my solver somewhat but it may be worth it since I will be placing 8 pieces at a time. I have yet to complete this solver so it should be interesting.