The eternity puzzle was devised by Mensan Chris Monckton and launched by ERTL in June 1999. Fiendishly difficult, the puzzle is the ultimate jigsaw, comprising of 209 unique tiles with no picture or symmetry. Each tile in the puzzle is made of 12 Drafter's Triangles - that is, the three angles are 30, 60 and 90 degrees. The challenge is to fit all of these tiles into a 12-sided shape aligned to a triangular grid, and was deemed so difficult that a £1,000,000 prize was offered. Monckton intended to cover this prize with the revenue raised from the sales of the puzzle and a 4-year insurance plan.
Unfortunately the problem was solved in rather less than 4 years and despite over a quarter of a million copies of the puzzle being sold Monckton ended up selling his house. Despite this setback he is planning Eternity 2, with a £2million prize. The first (and hence prize winning) solution came from Oliver Riordan and Alex Selby, both cambridge mathematicians, in May of 2000. The results were not verified until September and their solution remained secret until then. The only other correct submission was from a German chess master and former mathematician, Guenter Stertenbrin, who reached his solution in July 2000. In fact, he had found a 208-piece solution by September of 1999 (Alex only began work in November of that year and Oliver joined him the following January) but as Alex observes:
Of course one should realise that the last piece may well be the hardest. It depends on your method, but it could be that you need to find 1000 208-piece partial solutions before you expect to come across a complete solution.
The Eternity Puzzle is an example of an NP-complete problem: obviously it's easy once you know the answer, but if you don't then the potential list of solutions is daunting in size - all possible ways of arranging 209 objects. It is unsuprising that Riordan and Selby used a computer to assist in their attack of the problem. They observed that placing pieces without too much thought leads to difficulties once about 150 pieces have been placed, and options for placing more tiles become limited. So they developed a strategy to allow greater freedom in these later stages:
"The thing to remember about a puzzle like this is that some pieces are going to be easier to fit together than the others, and it's best to leave these easier pieces to the end. At the beginning there are lots of pieces and therefore lots of choices, and most of the times there wil be things that fit. And at the end that's not true. So, the idea is to make things harder for yourself at the beginning by using difficult pieces that will fit, and easier for yourself at the end - which is where you get stuck - by leaving the easy pieces to last. The thing then is to measure how easy it is to fit each piece. We had an actual measure of how well we were doing. We had a numerical score for how easy each piece was. If you filled in part of the puzzle and left a hole you'd add a score to show how good the shape of the hole was." - Riordan.
Armed with this statistical approach rather than trial and error, it took two weeks to solve the puzzle with a computer. Monckton had run brute-force tests on smaller puzzles before choosing the size of the commercial release, and observed that as the number of tiles increased, the time taken became greater. By choosing enough pieces, he would then have a puzzle that could not be solved in this way in a lifetime.
The problem was that this was only true up to a critical value. Beyond this point, having a larger number of tiles actually made the problem easier. The mathematicians found that this critical value was about 70: and estimated that with 209 pieces, there are something like 1095 solutions. At the critical level probability suggests there is only one solution: so the task of finding that one solution is much more difficult. By introducing more tiles, greater freedom in placing initial tiles is created as there is more than one correct approach, and it was this that Riordan and Selby were able to exploit in their technique of placing the difficult pieces first.
Another consequence of this result is that Monckton's occasional releases of information on where specific pieces should be placed were actually counterproductive. By using this information, you were reduced to only being able to find Monckton's solution - cutting yourself off from the rest of the 1095 believed to be possible.
Given their approach, Monckton will be able to make Eternity II even more fiendish, as whilst the statistical approach of assessing difficulty of pieces gives us a tool, it also illustrated how to make the problem that much more difficult - by adjusting the number of pieces the potential number of solutions can be reduced, whilst the introduction of constraints such as requiring a specific tile in a specific space could reduce the number to just 1 - the designer's.
Reference Material
- Http://www.eternity-puzzle.co.uk
- official site but lacking in mathematical information.
- http://www.msoworld.com/mindzine/news/miscellany/eternity.html#20
- MindZine Q&A session with Alex Selby.
- http://www.archduke.demon.co.uk/eternity/index.html
- Alex Selby's own site with links to media coverage and details of the solution.
- Mensa Magazine article "Eternity is not forever" from January 2001.