Eternity II puzzle

The Eternity II puzzle (abbreviated E2 or E II) is an edge-matching puzzle launched on 28 July 2007.[1][2] It was developed by Christopher Monckton and marketed and copyrighted by TOMY UK Ltd as a successor to the original Eternity puzzle. The puzzle was part of a competition in which a $2 million prize was offered for the first complete solution. The competition ended at noon on 31 December 2010, with no solution being found.

"E II" redirects here. For other uses, see EII (disambiguation).
The Eternity II puzzle

Description

The Eternity II puzzle is an edge-matching puzzle which involves placing 256 square puzzle pieces into a 16 × 16 grid, constrained by the requirement to match adjacent edges. It has been designed to be difficult to solve by brute-force computer search.

Each puzzle piece has its edges on one side marked with different shape/colour combinations (collectively called "colours" here), each of which must match precisely with its neighbouring side on each adjacent piece when the puzzle is complete. The other side of each piece is blank apart from an identifying number, and is not used in the puzzle. Thus, each piece can be used in only 4 orientations. There are 22 colours, not including the gray edges. Five of the colours are found exclusively in the 60 edge-pairs ("diamonds") in the outermost ring, i.e. between the border and corner pieces, while the other 17 are used in the remaining 420 "interior" edge-pairs. The colours are used evenly, with each of the 5 border colours used in exactly 12 edge-pairs, and each of the 17 inner colours used for either 24 edge-pairs (5 colours) or 25 edge-pairs (12 colours). The total number of edge-pairs is 480. One of the five border colours is not found on any corner piece, while all of the 17 inner colours are used at least once on a border piece.

There are 4 corner pieces (with two gray sides), 56 border pieces (with one gray side) and 142 = 196 inner pieces (with four coloured sides). Each piece has a unique arrangement of colours, and none of the pieces are rotationally symmetric, so each of the 256 × 4 = 1024 choices of piece and orientation results in a different pattern of edge colours.

The puzzle differs from the first Eternity puzzle in that there is a non-optional starter piece (a mandatory hint) which must be placed in a specified position and orientation near the center of the board.[3]

Two clue puzzles were available with the launch of the product, which, if solved, each give a piece position (hint) on the main 256-piece puzzle. Clue Puzzle 1 is a 36-piece square (6 × 6) puzzle and Clue Puzzle 2 is a 72-piece rectangular (12 × 6) puzzle. Two additional clue puzzles of the same dimensions were made available in 2008: the 36-piece Clue Puzzle 3 and the 72-piece Clue Puzzle 4. The rule book states that the puzzle can be solved without using the hints.[3]

Complexity

The number of possible configurations for the Eternity II puzzle, assuming all the pieces are distinct, and ignoring the fixed pieces with pre-determined positions, is 256! × 4256, roughly 1.15 × 10661. A tighter upper bound to the possible number of configurations can be achieved by taking into account the fixed piece in the center and the restrictions set on the pieces on the edge: 1 × 4! × 56! × 195! × 4195, roughly 1.12 × 10557. A further upper bound can be obtained by considering the position and orientation of the hint pieces obtained through the clue puzzles. In this case the position and orientation of five pieces is known, giving an upper bound of 4! × 56! × 191! × 4191 = 3.11 × 10545, yielding a search space 3.70 × 10115 times smaller than the first approximation.

To first approximation, the edge-matching constraint reduces the number of valid configurations by a factor of (1/5) for every border edge-pair and (1/17) for every inner edge-pair. The number of valid configurations is then approximated by 4! × 56! × 196! × 4196 × (1/5)60 × (1/17)420 ≈ 16.4, which is very close to unity. This indicates the puzzle has likely been designed to have only one or a few solutions,[4][5] which maximizes the difficulty: more solutions (looser constraints, e.g. less colours) would make it easier to find a solution (one of many), while tighter constraints decrease the search space, making it easier to locate the (unique) solution. Optimization of the number of colours has been investigated empirically for smaller puzzles, bearing out this observation.[6]

Competition and solution

After the first scrutiny date on 31 December 2008 it was announced that no complete solution had been found. A prize of $10,000 was awarded to Louis Verhaard from Lund in Sweden for a partial solution[7] with 467 matching edges out of 480.[8] Verhaard published three more partial solutions with the same number of matching edges.[7]

As of 30 January 2011, the official Eternity II site announces that "The final date for the correct solution of the Eternity II puzzle passes without a winner, and the $2m Prize for a correct solution to the Eternity II puzzle goes unclaimed."[9]

No verified complete solution to the Eternity 2 puzzle has ever been published. This includes Christopher Monckton's intended solution, which remains unpublished. Several fake solutions are known to have been circulated online.

History and design

The original Eternity puzzle was a tiling puzzle with a million-pound prize, created by Monckton. Launched in June 1999, it was solved by a computer search algorithm designed by Alex Selby and Oliver Riordan, which exploited combinatorial weaknesses of the original puzzle design.[10] The prize money was paid out in full to Selby and Riordan.

A puzzle with striking similarities to both eternity puzzles, the Diamond Dilemma, with a deadline in 1990, 10 years before the deadline of the original eternity puzzle, has fewer puzzle pieces, 160 compared with 209 and 256 for the first two eternity puzzles respectively, and yet Diamond Dilemma has not yet been solved in over 25 years.

The Eternity II puzzle was designed by Monckton in 2005, this time in collaboration with Selby and Riordan, who designed a computer program that generated the final Eternity II design.[11] According to the mathematical game enthusiast Brendan Owen, the Eternity II puzzle appears to have been designed to avoid the combinatorial flaws of the previous puzzle, with design parameters which appear to have been chosen to make the puzzle as difficult as possible to solve. In particular, unlike the original Eternity puzzle, there are likely only to be a very small number of possible solutions to the problem.[4] Owen estimates that a brute-force backtracking search might take around 2×1047 steps to complete.[12]

Monckton was quoted by The Times in 2005 as saying:

"Our calculations are that if you used the world's most powerful computer and let it run from now until the projected end of the universe, it might not stumble across one of the solutions."[11]

Although it has been demonstrated that the class of edge-matching puzzles, of which Eternity II is a special case, is in general NP-complete,[13] the same can be said of the general class of polygon packing problems, of which the original Eternity puzzle was a special case.

Like the original Eternity puzzle, it is easy to find large numbers of ways to place substantial numbers of pieces on the board whose edges all match, making it seem that the puzzle is easy. However, given the low expected number of possible solutions, it is presumably astronomically unlikely that any given partial solution will lead to a complete solution.

See also

References
  1. PRNewswire (26 July 2007). "Investegate |TOMY Announcements | TOMY: Eternity II Global Launch at Hamleys With US$2 ..." www.investegate.co.uk. Retrieved 5 October 2020.
  2. "Television interview with Christopher Monckton and Brendan Owen". Mornings with Kerri-Anne, Brendan Owen's channel, YouTube. 26 July 2007.
  3. Instruction booklet (PDF, archived), published on the official website
  4. Owen, Brendan (2007). "Eternity II - Design". Brendan Owen's Eternity II website. Archived from the original on 10 December 2007. Retrieved 9 November 2007.
  5. Ansótegui, Carlos; Béjar, Ramon; Fernández, Cèsar; Mateu, Carles (3 July 2008). "How Hard is a Commercial Puzzle: the Eternity II Challenge". Proceedings of the 2008 conference on Artificial Intelligence Research and Development: Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence. NLD: IOS Press: 99–108. doi:10.3233/978-1-58603-925-7-99. ISBN 978-1-58603-925-7.
  6. Willems, Daysel (24 June 2016). "On the Hardness of Framed Edge-Matching Puzzles" (PDF). Bachelor Thesis, Faculty of Science, University of Amsterdam.
  7. Verhaard, Louis. "EII Solver - Best results". www.shortestpath.se. Retrieved 9 October 2020.
  8. http://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel Link in Swedish
  9. "Eternity II". Archived from the original (official website) on 8 February 2010. Retrieved 30 January 2011.
  10. "Description of Selby and Riordan's Eternity I solver method". Alex Selby (and Oliver Riordan). 16 June 2007. Retrieved 16 June 2007.
  11. Elliott, John (4 December 2005). "£1m says this really is the hardest jigsaw". London: Times Online. Retrieved 9 November 2007.
  12. ""Solving" page on Brendan Owen's Eternity II website". Archived from the original on 10 December 2007. Retrieved 9 November 2007.
  13. Erik D. Demaine, Martin L. Demaine. "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity" (PDF). Retrieved 12 August 2007.
  14. "LGR - TetraVex and the Unsolvable Puzzle". YouTube. 5 February 2016.
  15. Takenaga, Yasuhiko; Walsh, Toby (15 September 2006). "Tetravex is NP-complete". Information Processing Letters. 99 (5): 171–174. doi:10.1016/j.ipl.2006.04.010. ISSN 0020-0190.

Software:

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.