Talk:Eternity II puzzle

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 
WikiProject Board and table games (Rated Start-class, Low-importance)
WikiProject icon This article is part of WikiProject Board and table games, an attempt to better organize information in articles related to board games and tabletop games. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 Low  This article has been rated as Low-importance on the importance scale.
 

NP-complete[edit]

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.

Number of Distinct Colors[edit]

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 (talkcontribs) 00:38, 13 October 2008 (UTC)

22 (+1) seems to be the correct number. The rule book lists 22 colors. I've also seen a partial list of the pieces that used 22 (+1) colors. 17 in hexadecimal is 23 which might explain the origin of that number. 217.9.26.52 (talk) 23:39, 6 January 2009 (UTC)
I've put this in the article: "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." I don't own the actual game, but I've deduced this much from the information available on the internet. —Preceding unsigned comment added by 89.216.147.154 (talk) 20:55, 3 December 2009 (UTC)

Official site inactive?[edit]

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)

2010 final date?[edit]

"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."

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)

Official solution announced?[edit]

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)

Yes, it is solved since 2012.
No it isn't. Joepnl (talk) 20:00, 14 August 2012 (UTC)

has the prize been renoced.[edit]

it is unclear weather the compation has closed or not can someone fix this.Confront (talk) 10:38, 18 May 2011 (UTC)

It is solved[edit]

See http://www.youtube.com/watch?v=ZLWBByFLAlc

That's not a solution Joepnl (talk) 20:00, 14 August 2012 (UTC)

Solution[edit]

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 (talkcontribs)

What solution? There is no full solution to date. —  HELLKNOWZ  ▎TALK 12:32, 27 November 2012 (UTC)
Hopefully the creator of the puzzle did not simply pick random combinations, but actually had a complete tiling which he broke to pieces, and so he holds the (or at least a) solution! 188.169.229.30 (talk) 08:16, 28 November 2012 (UTC)
This is a commercial product, so I'm sure the author has no intention of sharing the solution (if he has one) until one is found proper. Besides, sharing the actual piece patterns is illegal, as that is "pirating" the puzzle. —  HELLKNOWZ  ▎TALK 12:57, 28 November 2012 (UTC)
Did you expect the con-artist Monckton to be ethical? — Preceding unsigned comment added by 75.132.220.112 (talk) 23:58, 11 May 2015 (UTC)

Prize sum discrepancy[edit]

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)

External links modified[edit]

Hello fellow Wikipedians,

I have just added archive links to one external link on Eternity II puzzle. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—cyberbot IITalk to my owner:Online 06:17, 21 January 2016 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just added archive links to one external link on Eternity II puzzle. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—cyberbot IITalk to my owner:Online 04:21, 23 February 2016 (UTC)