Eternity puzzle
|
|
The eternity puzzle was a geometric puzzle with a million-pound prize, created by Christopher Monckton, who put up half the money himself, the other half being put up by underwriters Gaebel Watkins & Taylor of London.
The puzzle consisted of filling a large almost regular dodecagon with 209 smaller irregularly shaped smaller polygons. It was marketed to amateur puzzle solvers by Ertl Toys, and many copies were sold, with the game becoming a craze at one point.
Before marketing the puzzle, Monckton had taken advice from a number of mathematicians that the puzzle was very unlikely to be solved in the timescale specified for the competition, even with computer assistance. One estimate made at the time stated that the puzzle would probably take longer than the lifetime of the Universe to solve.
The puzzle was solved before the deadline by two Cambridge mathematicians, Alex Selby and Oliver Riordan, who had used an ingenious technique to vastly accelerate their solution. They realised that it was trivial to fill the board almost completely, to an "end-game position" where an irregularly-shaped void had to be filled with only a few pieces, at which point the pieces left would be the "wrong shapes" to fill the remaining space. The hope of solving the end-game depended vitally on having pieces that were easy to tile together in a variety of shapes.
They started a computer search to find which pieces tiled well or badly, and then used this data to alter their otherwise-standard backtracking search program to use the bad pieces first, in the hope of being left with only good pieces in the hard final part of the search. This heuristic approach paid off rapidly, with a complete solution being obtained within a couple of months of brute-force search on a couple of domestic PCs.
Paying off the prize-money forced Monckton to sell his house.
External links
- http://www.eternity-puzzle.co.uk/
- BBC News report on the solution (http://news.bbc.co.uk/1/hi/entertainment/992393.stm)
- An estimate of the complexity of the Eternity puzzle that turned out to be wrong (http://nrich.maths.org/public/viewer.php?obj_id=1354&part=index&refpage=articles.php)
- A detailed article on how the puzzle was solved (http://plus.maths.org/issue13/features/eternity/index.html)
- Discussion of the Eternity puzzle and related problems (http://mathpuzzle.com/eternity.html)
- Alex Selby's page on the Eternity puzzle (http://www.archduke.demon.co.uk/eternity/index.html)