I’ve been fascinated and hooked on Eternity II, the elusive edge matching puzzle, since I first heard about it in November 2009. It was released in 2007 as the successor to the original Eternity puzzle, and offers a $2M prize to the first person that solves it. Submissions are reviewed on Dec 31st each year with the final scrutiny date being Dec 31st, 2010. It remained unsolved as of Dec 31st, 2009.
The puzzle consists of 256 uniquely designed square tiles that have a pattern on each edge. There are 60 tiles that make up the border, consisting of 5 patterns. The inner 14×14 grid is made up using 196 tiles comprising 17 patterns. Here is a playable mini version of the puzzle. There is also an Eternity II Yahoo group where people have been discussing their ideas.
Christopher Monckton, the inventor has spent 8 years designing it, and has designed it in such a way that it cannot be solved by raw computing power alone. To give you an idea of the complexity of this puzzle, it’d take 360,000,000 times the age of the Universe to exhaust all of the possibilities using Tianhe-1, the worlds fastest supercomputer. That’s some seriously large numbers, considering the Tianhe-1 has a processing speed of 2,750 trillion instructions per second. There are a number of people writing backtracking solvers to try and find a solution, maybe hoping for a miracle and an extraordinary amount of luck, even with thousands of distributed Tianhe-1′s, the search for a computer generated solution appears quite futile.
Monckton has stated from the outset that a backtracking solver will not solve this puzzle, yet people persist. I myself have created a number of different programs to analyse the puzzle, backtracking solvers with a range of variable options to try and optimise the search. Even if you eliminate 99% of the search space, that still leaves 1% of 360,000,000 universes of time, so any reduction in search space would have to be exponentially better than a mere 99% reduction.
I’ve had a bit of time up my sleeve, and so I’ve dedicated a fair amount of time on this puzzle, trying to understand and figure out how it has been designed. I can’t explain why I’ve been so attached to it, I’ve never been so involved in a single project for an extended amount of time, with no apparent payoff. Sure the prize money would be life changing, but just the thought of being the first to solve such a challenging puzzle before anyone else would be a life changing achievement in itself.
I have looked at the 7 x $1M Millennium Prize Problems offered by Clay Mathematics Institute, though they are above my understanding of mathematics. The E2 puzzle falls into the P=NP puzzle domain, of which there is also a $1M millennium prize offered for solving P=NP.
I’ve always been fond of mathematics, it’s amazing how it appears in so many seemingly unrelated areas, from the golden mean ratio that the spiral of galaxies seem to follow, to fibonacci and the human body, plants, even language. Pretty much everything has a mathematical connection.
My philosophy has been that if I can figure out how E2 was designed, then there must be a logical way to solve it. My quest has led me to explore a number of different algorithms from simulated annealing, mutational algorithms, and an extensive analysis of the tileset to see if I could find any patterns within the dataset and comparing it against other puzzles with E2 like properties. I felt that I’ve been close to cracking the code a number of times, yet the sheer enormity of the puzzle has humbled me time and time again.
In my research I found that Monckton has published a number of Sudoku books, and invented the Sudoku-X variety in which both diagonals also have 9 unique digits. I recently purchased a copy of his Suduko X – Book 1. I was stunned when I read the following statement on page 9, ” I developed Sudoku X using the advanced computer algorithm that I’d originally constructed to help me design the Eternity puzzle.” I had a sneaking suspicion that it was connected to Sudoku somehow! Even so, trying to figure out how this can help solve the puzzle is still proving quite difficult. There is also no guarantee that E2 was designed in the same way that Eternity 1 was designed, though it seems there must be some connection between the two. It is not known whether the official solution to Eternity 1 had any sort of pattern, as the 2 solutions found were not the official solution, and they did not appear to have any distinctive pattern.
It would be cruel if there is no pattern or determinable design to Eternity II, and I can’t imagine it’d be a random puzzle even though it very much appears to be random. If it is indeed random, I’m not sure what kind of implications that’d have for Tomy for selling a puzzle that has no likelyhood of ever being solved.
I won’t yet elaborate on the finer details of my current ideas, as I may yet crack it (haha yeah right), but I may follow up in a future post if it hasn’t been solved and the prize has been withdrawn. With only 10 days or so remaining, to allow time for delivery, I’m not expecting any miracles, but am still giving it a go to the end!