Hi, I'm Jess. I use Python to craft web apps and sift data. I'm honing my full-stack development chops on Author Alcove.
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.
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.
@/\/ 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.
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
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 firstname.lastname@example.org
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
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
I found great ideas and discussing on your Web site.
Well done ! Thanks for that and keep on doing
Greetings from germany , Thomas
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.
but Eii is impossible :(
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 :-)
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.
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:
I bet it takes more than a second to solve it. ^^
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.
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…
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.
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.
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?
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
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…
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?
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…
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.
I tried this game once, but just didn´t get it. So how could you possibly solve this in 5 secs?
In 5 seconds????
I´ve no chance. I could not see and click so fast.
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.
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.
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.
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?
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.
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.
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.
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.
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
4x4x4x4x4 = 4096
This won’t guarantine solution because there may be multiple even sorts of pieces..
I didn’t mean to be aggresive :)
It’s always nice to see new ideas coming up :)
Code tag didn’t work as i thought… spaces are lost… There were eight pieces in 4×2 format…
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?
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)
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?
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
I haver order the game, but it will take two weeks to arrive!!
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.
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.
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.
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?
I tried to do this game what I`m too old to solve it, I think. Any advice how to get it solved ?
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
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 :) ).
Mihai, what kind of solver you have?
10×10 in 155secs is realy good time.
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:
|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|
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 :-)
eternity 2 pieces
i have a solution to eternity 2. how do i submit it?
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
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.
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.
Notify me of follow-up comments by email.
Notify me of new posts by email.
Browse the article archives.
You can have new articles delivered to your inbox.
© 2007-2015 GrokCode