This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||
|
While Demaine demonstrates that edge-matching puzzles in general are NP-complete, it does not mean that all specific edge-matching puzzles are necessarily NP-complete. (Consider as a counterexample trivial edge-matching puzzles with all pieces the same, which can be solved rapidly by trivial backtracking search, or the puzzle with all sides the same, which will be solved immediately by any search algorithm.) Is there any evidence that this particular puzzle has been deliberately constructed to be NP-complete?
Bonus question: is it possible to estimate the probability that a puzzle constructed by randomly coloring edgepairs of the puzzle in its assembled state before disassembling the tiles will be NP-complete, without solving an NP-complete problem to generate the probability itself? -- Karada 16:03, 28 August 2007 (UTC)
My understanding is NP-completeness cannot be determined for any one instance of the problem. For example, Chess can be solved with O(1) time, using the big-oh notation. Just have a table about the size of googol with all the positions in there, and look it up. NP-completeness only applies to certain class of problems when the problem solving time is measured in relation to the problem size in some measure. Eternity II has its rules printed out and the fixed set of pieces, so it does not have variable problem size, even tho it can placed into different classes of problems which indeed have variable problem size. 62.220.237.74 19:13, 15 September 2007 (UTC)
I was astonished by both comments. Both have a point and the first raise an important question. My summary is this. NP-complete refers to complexity class. This means that if a problem lies in this class, this is for every 'word' in the language of the input. For example, prime factorization may be outside of P, but finding the prime factors of 26=2*13 is trivial. Complexity is therefore used as a measure of how the difficulty scales to the size of the input, but does not refer to the difficulty of instances of the problem
About Eternity II, we are interested if it is tractable or not. It may well be, but there is strong evidence it may be not. Karada poses a very interesting question. To paraphrase it a liitle: "Was Eternity II constructed to be difficult?". And I might also be interested in designing an approach on how to decide on that.
Currently the article says there are 22 distinct colors, however, according to one of the references below: http://grok-code.com/10/e2-the-np-complete-kids-game-with-the-2-million-prize/ there are only 17, and possibly one of them is the gray color. Can anyone confirm this? —Preceding unsigned comment added by Randommuser ( talk • contribs) 00:38, 13 October 2008 (UTC)
The official website seems lousy with "Latest news" listing only two news back from 2007. No news about the 2008.12.31 scrutiny or the 2009 scrutiny just two weeks ago (the homepage hasn't even change the next scrutiny date from 2009.12.31 to 2010.12.31). Anybody knows a website which tells me more about the past two scrutiny results (best partial solutions, statistics etc)? Thanks. freeman ( talk) 22:08, 11 January 2010 (UTC)
This is somewhat unclear. It seems to suggest that 31st December 2010 is the final scrutiny date and therefore there will be no more after that. It then seems to suggest that only a complete solution will win the prize. Since Tomy we can presume don't have a time machine, they have no way of knowing if anyone will actually submit a completed solution by then, so this will imply the prize won't be awarded if no solution is found and submitted by then, but it isn't spelt out anywhere in the article Nil Einne ( talk) 00:04, 26 August 2010 (UTC)
Is the official solution already announced? If not, it should be stated somewhere. Until there is no solution, it is not clear if the puzzle eternity II can be solved at all. —Preceding unsigned comment added by 195.250.46.22 ( talk) 11:19, 16 February 2011 (UTC)
it is unclear weather the compation has closed or not can someone fix this. Confront ( talk) 10:38, 18 May 2011 (UTC)
See http://www.youtube.com/watch?v=ZLWBByFLAlc
If the prize is no longer applicable to claim, isn’t it ethical to announce the solution for the eternity ii puzzle? — Preceding unsigned comment added by 118.148.182.184 ( talk • contribs)
The article currently states the prize would be US $2m, while the relevant section in Monckton's article currently states £2m. I guess one of them should be changed. 188.169.229.30 ( talk) 08:09, 28 November 2012 (UTC)
This edit request by an editor with a conflict of interest has now been answered. |
Solution submissions
"Joshua Blackwood" has found a better solution of "468 matching edges out of 480" (12 breaks) than the existing record listed here by "Louis Verhaard" of "467 matching edges out of 480" (13 breaks). The demonstration was put together using the official puzzle, and the image can be found in the Reddit post, or the direct image here: https://i.redd.it/na9qdbwki6k51.jpg
[1] 24.151.79.134 ( talk) 23:01, 30 August 2020 (UTC)
References
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||
|
While Demaine demonstrates that edge-matching puzzles in general are NP-complete, it does not mean that all specific edge-matching puzzles are necessarily NP-complete. (Consider as a counterexample trivial edge-matching puzzles with all pieces the same, which can be solved rapidly by trivial backtracking search, or the puzzle with all sides the same, which will be solved immediately by any search algorithm.) Is there any evidence that this particular puzzle has been deliberately constructed to be NP-complete?
Bonus question: is it possible to estimate the probability that a puzzle constructed by randomly coloring edgepairs of the puzzle in its assembled state before disassembling the tiles will be NP-complete, without solving an NP-complete problem to generate the probability itself? -- Karada 16:03, 28 August 2007 (UTC)
My understanding is NP-completeness cannot be determined for any one instance of the problem. For example, Chess can be solved with O(1) time, using the big-oh notation. Just have a table about the size of googol with all the positions in there, and look it up. NP-completeness only applies to certain class of problems when the problem solving time is measured in relation to the problem size in some measure. Eternity II has its rules printed out and the fixed set of pieces, so it does not have variable problem size, even tho it can placed into different classes of problems which indeed have variable problem size. 62.220.237.74 19:13, 15 September 2007 (UTC)
I was astonished by both comments. Both have a point and the first raise an important question. My summary is this. NP-complete refers to complexity class. This means that if a problem lies in this class, this is for every 'word' in the language of the input. For example, prime factorization may be outside of P, but finding the prime factors of 26=2*13 is trivial. Complexity is therefore used as a measure of how the difficulty scales to the size of the input, but does not refer to the difficulty of instances of the problem
About Eternity II, we are interested if it is tractable or not. It may well be, but there is strong evidence it may be not. Karada poses a very interesting question. To paraphrase it a liitle: "Was Eternity II constructed to be difficult?". And I might also be interested in designing an approach on how to decide on that.
Currently the article says there are 22 distinct colors, however, according to one of the references below: http://grok-code.com/10/e2-the-np-complete-kids-game-with-the-2-million-prize/ there are only 17, and possibly one of them is the gray color. Can anyone confirm this? —Preceding unsigned comment added by Randommuser ( talk • contribs) 00:38, 13 October 2008 (UTC)
The official website seems lousy with "Latest news" listing only two news back from 2007. No news about the 2008.12.31 scrutiny or the 2009 scrutiny just two weeks ago (the homepage hasn't even change the next scrutiny date from 2009.12.31 to 2010.12.31). Anybody knows a website which tells me more about the past two scrutiny results (best partial solutions, statistics etc)? Thanks. freeman ( talk) 22:08, 11 January 2010 (UTC)
This is somewhat unclear. It seems to suggest that 31st December 2010 is the final scrutiny date and therefore there will be no more after that. It then seems to suggest that only a complete solution will win the prize. Since Tomy we can presume don't have a time machine, they have no way of knowing if anyone will actually submit a completed solution by then, so this will imply the prize won't be awarded if no solution is found and submitted by then, but it isn't spelt out anywhere in the article Nil Einne ( talk) 00:04, 26 August 2010 (UTC)
Is the official solution already announced? If not, it should be stated somewhere. Until there is no solution, it is not clear if the puzzle eternity II can be solved at all. —Preceding unsigned comment added by 195.250.46.22 ( talk) 11:19, 16 February 2011 (UTC)
it is unclear weather the compation has closed or not can someone fix this. Confront ( talk) 10:38, 18 May 2011 (UTC)
See http://www.youtube.com/watch?v=ZLWBByFLAlc
If the prize is no longer applicable to claim, isn’t it ethical to announce the solution for the eternity ii puzzle? — Preceding unsigned comment added by 118.148.182.184 ( talk • contribs)
The article currently states the prize would be US $2m, while the relevant section in Monckton's article currently states £2m. I guess one of them should be changed. 188.169.229.30 ( talk) 08:09, 28 November 2012 (UTC)
This edit request by an editor with a conflict of interest has now been answered. |
Solution submissions
"Joshua Blackwood" has found a better solution of "468 matching edges out of 480" (12 breaks) than the existing record listed here by "Louis Verhaard" of "467 matching edges out of 480" (13 breaks). The demonstration was put together using the official puzzle, and the image can be found in the Reddit post, or the direct image here: https://i.redd.it/na9qdbwki6k51.jpg
[1] 24.151.79.134 ( talk) 23:01, 30 August 2020 (UTC)
References