Several years ago, before I even started this blog, I got caught up in an effort to solve an impossible jigsaw puzzle with a prize of 1 million pounds attached. Needless to say, I did not win the prize, but I did find the whole experience somewhat addictive, in that as a programmer I could of course leverage my skills to try to solve the thing computationally.

The puzzle was called Eternity, and in the end it was solved sooner than expected (within 16 months), by Alex Selby and Oliver Riordan. Pictured here is their solution (one of only two found, of a potential set of millions). And yes, the 209 pieces of the puzzle are uniform in color. They are also reversible, very sharp and made of cheap nasty plastic.

Two people I particularly remember collaborating with (sharing ideas datasets etc) were Brendan Owen and Miroslav Vicher.

Eternity the Second

Anyhow, now I find myself in a tricky position— should I dive into the new version? Considering how much time I spent on the last one, I’m not sure I can afford to… I have enough of a things-to-do backlog as it is, and an open-ended project like this could really suck up any and all of my free time.

I did of course go out and buy a copy yesterday (the worldwide launch date), and I can’t help observing that this puzzle feels like it was made for a computer solver. There are 256 square pieces to be placed on a 16×16 grid such that adjacent edges match colors and pattern, as in the simple 4×4 example to the right. Note that this sample has only 4 different symbol/color combinations, whereas the full EternityII has 22 variants… making it extremely color-blind unfriendly!

So… I guess it’s obvious that I’m going to spend at least some of my time exploring this puzzle (I don’t really expect anyone else to see this as a productive use of my time) and it remains to be seen just how deeply immersed I become.

UPDATE: Brendan recently appeared on Australian TV with Christopher Monckton (the puzzle’s creator) to talk about Eternity II, here is a to the interview on Youtube, where Monckton states that 10,000 of the world’s fastest computers searching until the end of time might not find a solution.

Early Results and Observations

Although Eternity II features 22 different joining symbols (or "colors" for brevity’s sake) only 17 are used internally, with the remaining 5 used only in the border pieces. This means that you can encode the puzzle with only 17 colors, since we can reuse 5 for the border pieces. For example, the mini-puzzle above could be encoded using only 2 colors even though it is represented here with 4, since 2 of the colors only appear in border pieces and the other 2 only appear internally.

Implementing the most basic brute force algorithm in software gives impressive results very quickly, with puzzles up to 12×12 in size being very quick to solve (just a few seconds in many cases), but as you step to 13×13 and beyond things get much harder very quickly. Another approach is to vary the number of colors instead of the board size… for example a 16×16 puzzle with 25 colors is pretty fast to solve (under an hour) since there are fewer ways to join pieces when so many colors are used. Conversely, using many fewer colors also makes it easier to solve, since there will be so many ways to join pieces that multiple solutions are bound to exist. 17 appears to be about the right number of colors required to make E2 impossibly hard.

The brute force approach is quite simple and uses a concept known as backtracking, which means that we place pieces in a very organized way (eg top to bottom) and when we get to a point where we can not place another piece we undo the last piece placed and try the next available option. If none of those options work out (which they likely won’t) then we backtrack further and try again. It’s a very easy method to encode and understand; the problem with it is that we could potentially tile 95% of the board before we get stuck, and sometimes the backtracking will take us all the way back to the first piece we placed.

This entry was posted on Sunday, July 29th, 2007 at 12:08 pm and is filed under eternity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.