The Eternity Puzzle

looky

There was this jigsaw puzzle called Eternity which had a prize of 1 million pounds for solving it. That’s about 1.8 million US dollars.

The puzzle was designed by a guy named Christopher Monckton, and consists of a bunch of angular shapes which fit together on a giant gridlike board. As the Guardian said, “less of a jigsaw, more of a mosaic.” Because the various pieces fit together in so many different ways, finding a solution which fit all 209 pieces was next to impossible. Monckton offered the cash prize, awardable after a few months of the puzzle’s launch. The first solution to be received would get Monckton’s money.

Enter the puzzle geeks. The second this puzzle was announced, a huge effort formed around trying to solve it. A message board was formed, with a mailing list, full of geeks with computers who quickly reduced the pieces to simpler data representations and started working on algorithms to solve what is essentially a really crazy 2D “bin-packing problem.” Monckton estimated it would take about 4 years to solve, likely earning him more than the 1 million pound prize.

They cracked it in 16 months, twice. The award money went to the first solution, a team of two guys ( Alex Selby and Oliver Riordan ), although another man ( Guenter Stertenbrink ) solved it independently, with a different solution.

Obviously Monckton wasn’t planning on Eternity being solved so quickly. It was supposed to have taken over 4 years- he had planned to release “hint pieces,” pictures of the board with progressively more pieces on it. Ironically, complexity analyses have shown that this would have made the puzzle harder! At any rate, he had to sell his mansion (“Crimonmogate House in Aberdeenshire”) to pay out the prize money.

But the really funny thing is, it turns out Christopher Monckton is a big Nazi asshole. One of the reasons we barely heard about this puzzle, I mean aside from people not making a big deal about puzzles in general, and the prize money evaporating right after its launch, is that Monckton publicly said that everyone with HIV should be put in quarantine camps . Needless to say, his distributors didn’t want to be associated with his hateful bullshit.

Google for “Christopher Monckton AIDS” for more details on the incident… After this incident, I’ve seen him referred to as “British right-wing commentator Christopher Monckton.” Turns out he was an advisor to Thatcher.

Anyway, back to the puzzle:

Something that is interesting to me was the collaborative yet competitive nature of these message boards. To the puzzle enthusiasts, this was a bunch of money which they each considered their own. The Eternity puzzle would be solved eventually, but they had this stiff competition, spread thinly all over the world! However, these competitors were all fellow puzzle nerds.

Reading the boards is funny. The motivation to share solving techniques and hints is complex- there is the usual “look how smart I am to have thought of this,” as well as an altruistic desire to add to the “community.” But given the mercenary nature of this particular puzzle, there is also the hope that someone else will share their tidbit that hadn’t yet occurred to the first poster.

The puzzle itself is grossly complicated and tedious to solve. It’s made of a giant (hexagonal) grid of equilateral triangles which can be tiled with larger triangles… but each of those larger triangles is potentially cut in half (into a 30-60-90) on a random axis, and is not necessarily aligned with the tilings of other larger triangles. It makes more sense if you look at pictures of the puzzle.

Monckton planned to release “solution pieces” every so often after the first year, showing the board with one of the pieces placed correctly. The puzzle was solved too early for these to help- but ironically, these solution pieces would have made it harder. After a thorough analysis of the puzzle, the puzzle geeks determined that the puzzle was generated such that solution space was not as sparse as it could have been- not surprising, since calculating the puzzle to have exactly one solution would be an equivalent problem to solving an unknown puzzle in the first place! I’m assuming that the two solutions presented didn’t have any pieces in common with the “official” solution.

The architecture of solution approaches are fairly uniform- as you might imagine, a bit of dynamic programming (like the knapsack problem solution) is used- the tricky bit seems to be choosing the order of the pieces to add to the incremental solution. The winning approaches used a “goodness” of the piece to be added as a heuristic- amongst other things, the number of broken edges (the square edge of a 30-60-90 triangle) exposed to the perimeter of the piece would contribute to its “badness.”

Something that seemed obvious to me but I didn’t see thoroughly explored- representing the profiles of piece perimeters, thus enabling piece-piece interactions. What I mean is- most approaches I read simply tried to add a piece to a given tiling… instead of trying to add pieces together into larger and larger constructs. Sort of a reversed approach – the tricky part would then to grow the tiled area in a way which is “good”, that is making a tiled area which is mostly convex and similar in shape to the goal board shape. It would probably end up using a hill climbing approach to allow for temporary “bad” board shapes (to allow for new shapes being added).

But, whatever, the contest is over now, and I never did anything on it.

Links to solution sites:

Leave a Reply