Eternity II puzzle
Encyclopedia
The Eternity II puzzle, aka E2 or E II, is a puzzle
competition
which was released on 28 July 2007.
The competition ended at noon on the 31st of December 2010.
It was published by Christopher Monckton
, and is marketed and copyrighted by TOMY
UK Ltd. A $2 million prize was offered for the first complete solution.
which involves placing 256 square puzzle pieces into a 16 by 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 those can only be found on border and corner pieces and 17 only on so called inner pieces and the side of the border piece across from the gray colour. This puzzle differs from the first Eternity puzzle in that there is a starter piece which must be placed near the center of the board. (See PDF
rulebook on official website.)
Two Clue Puzzles were available with the launch of the product, which, if solved, each give a piece position on the main 256-piece puzzle. Clue Puzzle 1 is 6 by 6, with 36 pieces and Clue Puzzle 2 is 12 by 6, with 72 pieces. Two further puzzles were made available in 2008. Clue Puzzle 3 is 6 by 6, with 36 pieces, and Clue Puzzle 4 is 12 by 6, with 72 pieces.
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.115 × 10557.
The second scrutiny date was noon GMT on 31 December 2009. A communication from Tomy
Webcare stated:
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."
was a tiling puzzle
with a million-pound
prize, created by Christopher Monckton
.
Launched in June 1999, it was solved by an ingenious computer search algorithm designed by Alex Selby and Oliver Riordan, which exploited combinatorial weaknesses of the original puzzle design. The prize money was paid out in full to Selby and Riordan.
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. 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.
Owen estimates that a brute-force backtracking search might take around 2 steps to complete.
Monckton was quoted by The Times in 2005 as saying:
Although it has been demonstrated that the class of edge-matching puzzle
s, of which Eternity II is a special case, is in general NP-complete
,
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.
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
competition
Competition
Competition is a contest between individuals, groups, animals, etc. for territory, a niche, or a location of resources. It arises whenever two and only two strive for a goal which cannot be shared. Competition occurs naturally between living organisms which co-exist in the same environment. For...
which was released on 28 July 2007.
The competition ended at noon on the 31st of December 2010.
It was published by Christopher Monckton
Christopher Monckton, 3rd Viscount Monckton of Brenchley
Christopher Walter Monckton, 3rd Viscount Monckton of Brenchley is a British politician, public speaker, former newspaper editor and hereditary peer. Formerly a member of the Conservative Party, Monckton has been the Head of the Policy Unit for the UK Independence Party since November 2010. He was...
, and is marketed and copyrighted by TOMY
TOMY
is a Japanese toy, children's merchandise and entertainment company created from the March 2006 merger of two companies: Tomy and long-time rival, Takara...
UK Ltd. A $2 million prize was offered for the first complete solution.
Puzzle mechanics
The Eternity II puzzle is an edge-matching puzzleEdge-matching puzzle
An edge-matching puzzle is a type of tiling puzzle involving tiling an area with polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match....
which involves placing 256 square puzzle pieces into a 16 by 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 those can only be found on border and corner pieces and 17 only on so called inner pieces and the side of the border piece across from the gray colour. This puzzle differs from the first Eternity puzzle in that there is a starter piece which must be placed near the center of the board. (See PDF
Portable Document Format
Portable Document Format is an open standard for document exchange. This file format, created by Adobe Systems in 1993, is used for representing documents in a manner independent of application software, hardware, and operating systems....
rulebook on official website.)
Two Clue Puzzles were available with the launch of the product, which, if solved, each give a piece position on the main 256-piece puzzle. Clue Puzzle 1 is 6 by 6, with 36 pieces and Clue Puzzle 2 is 12 by 6, with 72 pieces. Two further puzzles were made available in 2008. Clue Puzzle 3 is 6 by 6, with 36 pieces, and Clue Puzzle 4 is 12 by 6, with 72 pieces.
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.115 × 10557.
Solution submissions
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 Anna Karlsson from Lund in Sweden for a partial solution with 467 matching edges out of 480.The second scrutiny date was noon GMT on 31 December 2009. A communication from Tomy
TOMY
is a Japanese toy, children's merchandise and entertainment company created from the March 2006 merger of two companies: Tomy and long-time rival, Takara...
Webcare stated:
- "I can now confirm that although we received many excellent entries we have not received any complete entries therefore, Eternity II still remains unsolved and the clock is now ticking to claim the $2m prize. All solutions received this year will be locked away in a vault until the final scrutiny date, 31st December 2010. On that day, all solutions will be opened in date order received and the first person with a complete solution wins $2million."
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."
Solution
A complete solution is still missing. Therefore it is unproven that the puzzle is solvable at all.History and puzzle construction
The original Eternity puzzleEternity puzzle
Eternity is a tiling puzzle created by Christopher Monckton and launched by the Ertl Company in June 1999. Consisting of 209 pieces, it was marketed as being practically unsolveable, with a £1 million prize on offer for whoever could solve it within four years. The prize was paid out in October...
was a tiling puzzle
Tiling puzzle
Tiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps . Some tiling puzzles ask you to dissect a given shape first and then rearrange the pieces into another shape...
with a million-pound
Pound (currency)
The pound is a unit of currency in some nations. The term originated in England as the value of a pound of silver.The word pound is the English translation of the Latin word libra, which was the unit of account of the Roman Empire...
prize, created by Christopher Monckton
Christopher Monckton, 3rd Viscount Monckton of Brenchley
Christopher Walter Monckton, 3rd Viscount Monckton of Brenchley is a British politician, public speaker, former newspaper editor and hereditary peer. Formerly a member of the Conservative Party, Monckton has been the Head of the Policy Unit for the UK Independence Party since November 2010. He was...
.
Launched in June 1999, it was solved by an ingenious computer search algorithm designed by Alex Selby and Oliver Riordan, which exploited combinatorial weaknesses of the original puzzle design. The prize money was paid out in full to Selby and Riordan.
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. 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.
Owen estimates that a brute-force backtracking search might take around 2 steps to complete.
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."
Although it has been demonstrated that the class of edge-matching puzzle
Edge-matching puzzle
An edge-matching puzzle is a type of tiling puzzle involving tiling an area with polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match....
s, of which Eternity II is a special case, is in general NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
,
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.
External links
- The homepage for Eternity II
- Open Source Eternity II Editor/Solver software
- Open Source Eternity II puzzle software
- E2Lab : Free Eternity II Editor/Solver software
- E2Solver : Open Source Eternity II puzzle solver
- Description of Eternity II and discussion of solvers
- Description of the Eternity II solver used by Anna Karlsson