Discussion On
E2: The (NP-Complete) Kids’ Game with the $2 Million Prize

by in Fun Projects

53 Comments

  1. Shivendu
    Sunday, June 2934, 2008

    Very Nice Post The Eternit 2 (E2) puzzle has attracted the programmers and mathematicians because i hope this is the first puzzle whose prize is $2 million.

    Reply
  2. /\/
    Thursday, December 1808, 2008

    These algorithms do not seem really efficient, a basic prolog brute force one achieves better performances. I assume it is because of the built in backtrack.

    Reply
  3. Jess Johnson
    Friday, December 1919, 2008

    @/\/ The recursive algorithm may be causing a performance hit. I’m curious how much faster the prolog test ran? Also, I’m not exactly testing on a state of the art box, so if your test is running on better hardware, that could be causing the difference.

    Reply
  4. Billigflug
    Monday, December 2204, 2008

    The Eternit 2 (E2) puzzle is very famous because of it’s prize is $2 million prize for being the first to solve it.
    keep up your good work
    I will be a regular reader of ur blog

    Reply
  5. Miquel
    Tuesday, January 2053, 2009

    I haver order the game, but it will take 2-3 weeks to arrive. Does anybody has a list of the pieces in a txt file? I will be very gratefully mcubel@gmail.com

    Reply
  6. dPUNiSH3R
    Tuesday, January 2730, 2009

    My new (not finished) solver outperform these benchmark results… Solver is implemented in Delphi.
    bench 8×8 in 246 seconds! http://img218.imageshack.us/img218/8536/bench8x8pi5.jpg

    Reply
  7. P-E-X
    Thursday, May 2852, 2009

    My solver has solved 10×10 in seconds, but sometimes it takes minutes :-)
    With one hint piece, 5 edge types, 18 center types.
    It solves about 2-6 million pieces at second on Intel Core 2 Duo 4300.

    Java is great

    Reply
  8. Thomas , Zauberer Zauberkünstler
    Sunday, May 3111, 2009

    Hi there,
    I found great ideas and discussing on your Web site.
    Well done ! Thanks for that and keep on doing
    Greetings from germany , Thomas

    Reply
  9. dPUNiSH3R
    Sunday, May 3153, 2009

    P-E-X How long it takes to solve 10×10 with 3 hints? And the 8×8 with 2 hints? (With the puzzle definition used here in GrokCode benchmarks)
    After tuning and optimizing my code, I dropped solving time… example: 8×8 2 hints from 246 seconds (see above) now in less than 5 seconds! Starting with 4 possible corners in a quad core and 9-10 million pieces/second performance solver, invalid starter corner detected in less than 81 seconds and a solution found in 5 seconds with right corner.
    http://img193.imageshack.us/img193/4313/grok8x82hints.jpg

    but Eii is impossible :(

    Reply
  10. P-E-X
    Sunday, May 3158, 2009

    I benchmarked my solver. I don’t have ms timing (aiming for high) and mine supports only one hint piece (still under development)

    All test were run on single thread, no multithreading supported at the moment, on Core 2 Duo 4300 1,8ghz

    50 Runs 8×8, one hint piece, 5 border types, 18 center types:
    All 50 runs took less than second, timer was always: 0 seconds

    50 Runs 10×10, one hint piece, 5 border types, 18 center types:
    – Most of runs took less than second to complete.
    – Longest run: 39secs
    – There were only few of those long runs 39, 26, 8 secs all other where lesser than that.
    – Average time: 3,08 sec for 50 runs.

    Use the power (of the algorithm)
    Mine has always correct corner piece :-)

    Reply
  11. P-E-X
    Sunday, May 3104, 2009

    I started six runs on 11×11 (not same data), one hint piece, 5 border types, 18 center types took… One have completed: 2 min 43 sec, but others may take hours or days… not waiting those… 10×10 has only 100 pieces… 16×16 has 256… and each increase 1-10 times the time needed for solving, so lots of improvement has to happen before Eternity 2 is solved.

    Reply
  12. dPUNiSH3R
    Sunday, May 3101, 2009

    Board size (pieces quantity) is not the main cause of complexity, the pieces types and patterns quantity are more determinant.

    Please run your solver with these pieces/patterns and use the first hint only:
    http://grok-code.com/downloads/B8x8With2Hints.txt

    I bet it takes more than a second to solve it. ^^

    Reply
  13. P-E-X
    Sunday, May 3144, 2009

    Aah, now i saw the testdata. I need to make little modifications to code for the hint piece. Offcourse with this data it will take more time to complete, but i am pretty sure that it will be more efficient than Doc Smith or Joel algorithms.

    Reply
  14. P-E-X
    Friday, June 1249, 2009

    Haven’t got time to work with the solver, but with random data 8×8 table and 1 one hint piece i waited few hours without result. dPUNiSH3R your algorithm can handle in about 3 minutes? That’s fast…

    Reply
  15. dPUNiSH3R
    Friday, June 1203, 2009

    P-E-X if you review my post you will see that my results were using the 2 hint pieces. (“8×8 with 2 hints” benchmark used here)

    Summary of my results:

    2 hints: starting with right corner then 5 seconds to solve, starting with a no solution corner then 120 seconds to detect no solution. http://img193.imageshack.us/img193/4313/grok8x82hints.jpg

    If I use only 1 hint (the first hint): starting with right corner then 16 minutes to solve, bad corner then 164 minutes to detect no solution.
    http://img20.imageshack.us/img20/6752/grok8x81hint.jpg

    I run my solver using 4 instances running in parallel (in a quad core), each instance with a different corner piece fixed (4 possible), so I solve it in 5 seconds with 2 hints, and 16 minutes with 1 hint.

    Use the same test puzzle for a better comparison.

    Reply
  16. P-E-X
    Wednesday, June 2432, 2009

    6×6 puzzle can be solved in few milliseconds… about 150ms between values where 1 – 300ms.
    but 8×8 wasn’t finished after 5 hours on single core. I think i must look the loading algorithm if there is something wrong.

    dPUNiSH3R your algorithm can solve 8×8 with only 50 million tests?

    Reply
  17. P-E-X
    Monday, July 603, 2009

    I had to make major modifications to algorithm. First i had a rotating table which worked, but was not efficient enough multiple cores and fixed start pieces seem to be the way. I had also randomization bug (pieces were not rotated). Last i had loading problem for test data. Now almost all features are implemented and working. So better results are comming :-)

    Grok 8×8 with 2 hints (Piece order is randomized and randomly rotated)
    Six runs average 26 min (Min 10 – Max 52)

    With correct corner piece best time is 3,30 min

    Reply
  18. Gummistiefel
    Thursday, July 1624, 2009

    As my daughter and I eagerly unwrapped the package our copy of Eternity II came in we couldn’t wait to rip off the cling film and get going. Four hours later we were still at the dining table having zoomed ahead on several occasions, only to find ourselves having to backtrack again.

    The feeling is just like when you find you have one stray white cube in the middle of a face of green squares on your Rubics Cube…

    Reply
  19. Chilly
    Wednesday, July 2941, 2009

    Hi,

    I must be missing something here. For the Grok 8×8, starting with a particular corner and ignoring hints I make the number of possible branches after placing 24 further tiles to make a 5×5 square approximately

    8^3 x 7^3 x 6^2 x 2^16 = 414 billion

    so even solving at 10 million branches per second would take several hours?

    What am I missing?

    Reply
  20. P-E-X
    Wednesday, July 2942, 2009

    Chilly, you don’t have to check all possible combinations, only those which can be possible… like Corner pieces must be at the corner (4 start pieces, no need to check pieces 5-64 and all of their combinations where those pieces are at the corner)… piece next to current piece must have the same edge…

    Reply
  21. Chilly
    Thursday, July 3011, 2009

    P-E-X. Thanks for your reply. Yes, I was allowing for that. For the grok 8×8 there are 24 edges but only 3 different colours, so on average 8 possible candidates for first 3 edges, then 7 for the next 3. For centre pieces where you already have 2 sides to match the expected number of candidates is 34 (pieces left) x4 (rotation) /8^2 = 2.125, since there are 8 different colours on centre pieces, hence the 2^16 in my formula. I threw together some code to do a recursive backtrack and that verified my numbers. I think the answer is that the hint pieces reduce the number of nodes (by piece 25) from 400bn by a factor of 8^4, so to around 100m. I found a paper that suggests most alogorithms handle around 4m nodes per second, so with the hints the run-time is OK. But I still don’t understand how dPUNiSH3R can solve in 5 secs. Implication is that there are some short cuts, which is what I’m interested in.

    Reply
  22. Stromtarif
    Tuesday, August 1835, 2009

    I tried this game once, but just didn´t get it. So how could you possibly solve this in 5 secs?

    Reply
  23. der-banker
    Tuesday, August 2558, 2009

    In 5 seconds????
    I´ve no chance. I could not see and click so fast.

    Reply
  24. Anthony Vegas
    Saturday, November 750, 2009

    I read a few descriptions about this puzzle and apparently each of the 256 pieces are numbered on the back. I assume these have been ‘randomly numbered’ which may represent an easy solution to the puzzle namely computers don’t do random very well, standard procedure for randomness is to use the clock cycle as a ‘seed’ I’m not a cryptographer but I would be willing to bet there is a pattern in the resulting numbers generated.

    Reply
  25. Les in Ashburn
    Friday, November 1336, 2009

    Anthony is on to something.
    Take add in all the clue pieces and the easter egg on the box, and you have around 16 free pieces placed.
    If a pattern could be discerned from those 16 fixed locations, one could unrandomize the numbers and find the solution Monckton used as start point.

    Reply
  26. David in Atlanta
    Wednesday, December 3035, 2009

    Les in Ashburn,

    What easter egg on the box? How did you get 16 fixed locations? I Have the main one in the middle and the four clue puzzle ones.

    Reply
  27. Kuyler
    Sunday, January 354, 2010

    I bought E2 this weekend. I’ve noticed with mine that each half shape is not perfectly cut, so when joined together they do not make symettrical shapes, however there seems to be a father and mother piece which seems to make it a little easier when looking for a specific colour, for instance, The yellow circle with the purple cross is not symmetrical when two pieces put together, however you can discount all the larger pieces needed to complete the cross, or am I wrong and was just V. unlucky to have a badly cut board?

    Reply
  28. David in Atlanta
    Sunday, January 307, 2010

    Each piece is printed on the cardboard you punched them from, not next to the piece that they should match with. Symmetrical would not matter as long as the patterns match. All boards have some pieces that were cut a little bit off. Its nothing to worry about. Just dont look into the way they are cut too much as it does not mean anything.

    Reply
  29. P-E-X
    Tuesday, January 557, 2010

    If you are thinking the board like chess board… white and black places… in correct solution there must be equal number of each style piece in black and white places.

    If somebody could sort these pieces to two piles (white & black) both containining equal amount of each style. That could be start for the solution.

    Reply
  30. /\/
    Tuesday, January 524, 2010

    Why would we assume that such a basic pattern as the one underlying a chess board (w/b/w/b/w/b…) is somehow related to eternity II ? Even if it was proven true, we wouldn’t be able to infer that we ought to have the same number of pieces in each pile. And even if that was the case, we would still have no idea of how to order the pieces.
    For what we know, the placement pattern (in the sense that knowing it would give us the rules required to place the pieces into X piles) can be anything.

    Reply
  31. P-E-X
    Wednesday, January 600, 2010

    This was an idea…


    X X X X
    XW3 3B1 1W4 4BX
    4 3 2 1

    4 3 2 1
    XB1 1W3 3B1 1WX
    X X X X

    Style White Black
    1 4 4
    2 1 1
    3 3 3
    4 2 2

    Number of pieces must be even
    X:s aren’t noted here because they dont got any pair.

    Thoughts:
    Maybe pieces could be sorted to two piles black and white. Then try to solve the piece locations. Number of possible pieces is only half of it used to be.
    8x8x8x8x8 = 32768
    But:
    4x4x4x4x4 = 4096

    This won’t guarantine solution because there may be multiple even sorts of pieces..

    Reply
  32. /\/
    Wednesday, January 604, 2010

    I didn’t mean to be aggresive :)
    It’s always nice to see new ideas coming up :)

    Reply
  33. P-E-X
    Wednesday, January 617, 2010

    Code tag didn’t work as i thought… spaces are lost… There were eight pieces in 4×2 format…

    _1_
    2W3
    _4_

    Reply
  34. David in Atlanta
    Wednesday, January 629, 2010

    P-E-X,

    I am interested in what you are talking about, but I am not following what you are saying at all. Can you break down the meaning behind your last post?

    Reply
  35. P-E-X
    Wednesday, January 643, 2010

    My ascii art was raped by site :(

    I mean that if board is divided to white and black places like chessboard.
    Any of white pieces won’t touch any of white pieces and
    any of black pieces won’t touch any of black pieces.
    Thats why each white must have 4 black pair pieces and
    yeah black piece must have 4 white pieces…

    Thats pretty clear…

    Now in Eternity II each complete pattern is divided into two pieces. In this case to white and black piece.
    Thats why total sum of each pattern must be same in black and white pieces…

    Now if somebody could sort these pieces really fast to even piles it could be found.

    Another thing if the piles ain’t even the puzzle is unsolvable… (i used this in my solver, but not very good speedup… maybe with larger board it could help more)

    Reply
  36. David in Atlanta
    Wednesday, January 606, 2010

    How would solving for these two types of pieces be any faster than solving the puzzle itself? How would you define a piece so that it would fit ONLY into one of the two?

    Reply
  37. P-E-X
    Wednesday, January 646, 2010

    David in Atlanta,

    I didn’t find a way to sort these pieces… But somebody may…
    I don’t know how to sort sets…

    If pieces are sorted the solving may be exponentialy more efficient….
    8×8×8×8×8 = 32768
    But when number of possible pieces is halved…
    4×4×4×4×4 = 4096

    At least this can be used to track faulty places pieces

    Reply
  38. Versicherungsblog
    Friday, February 1206, 2010

    I haver order the game, but it will take two weeks to arrive!!

    Reply
  39. Rob
    Thursday, March 1142, 2010

    dPUNiSH3R,
    I read your results on the GROK 8×8.
    It’s impressive that you found a solution in 5 seconds (with the right corner piece set).
    But it may be that this was just by chance.
    The fact that it takes 80 seconds to find out that/if there is no solution (with the wrong corner piece) is more interesting, since that means you exhaustively searched the GROK 8×8 in 80 sec (x4 for the possible corner choices).

    I wonder if you made more progress since then (getting faster), and also which search order you use.
    I also wonder if you found the second solution (my solver found 2 solutions, as part of a 25 sec exhaustive search).
    With one hint, and exhaustive search of GROK 8×8 takes an hour. Same result : 2 solutions.

    Also, I wonder if anyone managed to solve the GROK 10×10 (with or without the 3 hints) by now.

    My solver was cranking on it for 2 days, with interesting results, but no solution.
    I estimate that I searched only 1 % of the realistic (probably) solution space.

    Thanks

    Rob

    Reply
  40. Doc Smith
    Wednesday, May 2604, 2010

    Didn’t have time for eternity 2 during the last years and were suprized my solver is discussed here. By the way, there was an eternity I back in 1999 which was completely solved, there are 12 known solutions, 9 of them from me (unfortunately I wasn’t the first). After reviewing my eternity II code after 2 years I decided to rewrite the thing in Java – haven’t seen Joels work at that time. Some comments: New processors (I7, intel q9550) perform very good for Java, there is no more any performance penalty, specially if you use jdk-6u20-windows-x64.exe. 64-bit is about 30% faster, jdk-6u20-windows-x64.exe is 10% faster than jdk-6u14-windows-x64.exe
    and much faster than jdk5 versions. Using 4 cores you can reach about 100.000.000 nodes per second on a 3.4 Ghz Q9550. Order of piece placemant is very important, specially if hint pieces are used. The whole search space can significantly be reduced, this explains the different results. The time for finding a solution is completely random – the time for searching the whole search space is not. The task for finding a “almost complete” but not perfect solution is completely different from the task searching for a complete solution – different techniques are required. I will try to write some code for this purpose.

    Reply
  41. Doc Smith
    Wednesday, May 2646, 2010

    After seeing Joels code: This is a one to one port of my C++ code, very similar to what I tried myself first. But after that I saw that the quite complex optimization which worked well for C++ doesn’t help in Java. So my new Java code is more similar to the original code of Marc Lebel, which suprizingly is about 10% faster than the one to one port – and almost the same speed as the original C++ version. A further modification is to support finding maximal partial solutions – as far as I know there was a 10.000 prize for finding a 467 correct edges partial last year. I allow with some small probability the placement of not completely fitting pieces during the search in order to get some promizing piece placements with only a few nonfitting edges, and then try to optimize these by exchanging pieces. Some data structures needed to be adapted in order to support this.

    Reply
  42. Mihai Stanimir
    Thursday, June 1038, 2010

    Hi guys, you’re doing a great job here!

    Like you all, I decided to write my own solver and thought I could share some benchmarks for 5 border edge types, 17 interior edge types (like the original game):
    9×9 table – average time: 2.5 seconds
    10×10 table – average time: 155 seconds

    What are the best times for these settings yet?

    Problem probably cannot be solved for 16×16 but you don’t know until you try. What’s the best solver yet?

    Regards,
    Mihai

    Reply
  43. Zauberei
    Thursday, July 2944, 2010

    I tried to do this game what I`m too old to solve it, I think. Any advice how to get it solved ?

    Reply
  44. Hugo Peixoto
    Monday, August 239, 2010

    Rob,

    I also got two solutions for the 8×8 problem, both with the same corner piece.

    To search the whole grok8x8 dataset, with 2 hints my current times for each corner piece are:

    corner 1: 108.546374 secs (2 solutions)
    corner 2: time: 92.717353 secs (0 solutions)
    corner 3: time: 80.345329 secs (0 solutions)
    corner 4: time: 101.156403 secs (0 solutions)

    With just one hint it took about 20 minutes or so to find the first solution,
    and 1751.234429 secs to finish scanning the first corner.

    Unrelatedly, I find it funny this is being discussed on a two year old blog post. :P

    Reply
  45. Hod
    Monday, August 3019, 2010

    Hi Guys,
    I’m looking for clue3&4, unfortunatelly these were not released in my country, and I haven’t found them is webshops either. So I would like to buy in any form (box, piece photos, whatever :) ).

    Regards!

    Reply
  46. P-E-X
    Monday, August 3026, 2010

    Mihai, what kind of solver you have?
    10×10 in 155secs is realy good time.

    Reply
  47. David L
    Friday, October 2245, 2010

    Hi everyone, this is the first time I have seen this page, and seems very interesting. I was just wondering, how to interpret the solutions that both programs (Doc Smith’s and Joel’s) returns. I have looked on the internet, but have not found how to interpret them. If anyone can help, it would be greatly appreciated. Thanks in advance, David
    PD: Solution file is of style:

    Solution 1:

    |00| |00| |00| |00|
    |00| |01| |01| |02| |00|
    |02| |04| |04| |02|
    |00| |04| |04| |03| |00|
    |02| |03| |03| |01|
    |00| |03| |04| |03| |00|
    |02| |04| |03| |01|
    |00| |01| |02| |01| |00|
    |00| |00| |00| |00|

    Reply
  48. Angela
    Tuesday, November 2335, 2010

    what country are you in…the 3rd and 4th clue puzzles were not released in New Zealand but I contacted the distributors of the first two puzzles here directly and bought the ‘demo’ copies sent to them….and of course solved them….so I have 5 pieces towards one solution which is a good start….I have a level of understanding with regards to the possible combinations for this puzzle(astronomical) and no programming skills whatsoever and would love to just be ‘lucky’ solving it the way any jigsaw is solved by putting the right pieces together but do not wish to have the big cardboard pieces to carry around everywhere and really want to put a simple programme on my laptop that can ‘save’ pieces in set places and I could re-open to continue the puzzle ….it would also be nice if it could sort pieces so you can just se pieces that have a specific shape on them to save time but I have yet to find anything that does this….you would think Tomy would make an online site (even paid membership) or an electronic version what a marketing failure….and no it wouldnt have to contain solution code just let the person print thier finsihed product and buy the cardboard version and transfer the info. If anyone can advise where I can get this I’m keen to buy one still got a month :-)

    Reply
  49. e2pieces.txt
    Saturday, December 1853, 2010

    eternity 2 pieces
    http://rapidshare.com/files/438041081/e2pieces.txt

    Reply
  50. micheal marshall
    Tuesday, December 1308, 2011

    i have a solution to eternity 2. how do i submit it?

    Reply
    • fred gannett
      Wednesday, September 2516, 2013

      It’s not the answer – it’s how you got there that would be intersting at this stage. Luck or long search ?
      Ping me to discuss
      gannett [at] Spikynorman.net

      Reply
  51. Angela
    Tuesday, December 1323, 2011

    Saw the comment regarding someone having a solution and wondering where to send it. Tomy(distributors) advised me to contact the maker via email and gave me an address I sent an email three times never got a response so I guess your out of luck….the winnings were meant to go to the closest entry after the final deadline but surprisingly nothing appeared in the papers etc so I’m guessing it didnt happen and they just kept the prize….sucks for those of us with a solution etc.

    Reply
  52. fred gannett
    Wednesday, September 2509, 2013

    It is 2013 and not aware of any published E2-256 solutions as yet. The competition has closed with partial a prize issued. Me, I am still hunting with a few ideas and a Hex-core i7 + Cuda on a GPU to explore with. Want to help climb this digital Everest ? Ping me at address below.

    Also I am looking to buy a complete Clue 4 box. Sealed or parts still in sheets prefered. Ping me on gannett [at] Spikynorman.net – put E2 in the subject line to avoid the spam filters.

    Gannett

    Reply

Leave a Reply