Talk:Eternity II puzzle

Computing Start‑class Low‑importance

	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.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-importance on the project's importance scale.

Board and table games Start‑class Low‑importance

	Games portal 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.Board and table gamesWikipedia:WikiProject Board and table gamesTemplate:WikiProject Board and table gamesboard and table game articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-importance on the project's importance scale.

NP-complete

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

Official site inactive?

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)[reply]

2010 final date?

"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)[reply]

Official solution announced?

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)[reply]

Yes, it is solved since 2012.

No it isn't. Joepnl (talk) 20:00, 14 August 2012 (UTC)[reply]

has the prize been renoced.

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

It is solved

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

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

Solution

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)

What solution? There is no full solution to date. — HELLKNOWZ ▎TALK 12:32, 27 November 2012 (UTC)[reply]

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)[reply]

Prize sum discrepancy

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)[reply]