Eternity II Odds

I got to thinking about the Eternity II puzzle again this week. I've made several previous attempts at solving it, but they have all gone down in flames. This time my idea this time was to build up one edge of the puzzle, that is 16 square tiles all against one side. Build up one edge, and set it aside. Then build another edge, and another. Build all possible edges, and then when you have a complete set mix and match until you find a set that will make a complete square. That is it will use all four of the corner pieces and all 56 of the edge pieces, and it will use each piece only once.

This depends on being able to generate all of the possible complete edges. That should not be too hard. We have 56 edge pieces, and 22 possible colors, so that's something less than 3 possible matches for each piece. We have to find 15 edge pieces and one corner piece to build a complete edge. So that is like 3 to the power of 16. 3 to the 4th is 81, 81 squared is just a little greater than 6400 (which is about 3 to the 8th). Square that again gives us 3 to the 16th. 6400 squared is 64 squared times 10,000. 64 squared is 4096. Call it 4,000. So 4,000 times 10,000 is 40 million. So 3 to the 16th is roughly 40 million.

I have a computer that can do a billion operations a second. It should be able to crank this out in short order. I've been thinking about this all week, and last night I finally dug out some old code that could be made to do this job with minimal modification. This morning I beat it into shape and fired it up and it ran and ran and ran. Hmmm. Something is not right. It has gone way past 40 million. What's going on here?

I go back and look at the index I generated and I find the problem. The sneaky devils who designed this puzzle didnot use all 22  colors for the edges between adjacent edge pieces, they only used five. Which means that for each piece there are 12 possible matches (60 divided by 5), not 3. So the total possible complete edges is more like 12 to the 16th power, which is like 100 Quintilian, which is a billion times bigger than 40 million.

So million, billion, quintilian, we've got a lightning fast computer, it should be able to handle this right? Well, maybe so, maybe no. Say it can do a billion operations a second. Then it can do about 100 trillion operations a day, or 10 quadrillion operations a year. To perform a 100 quintilian operations then would take ten thousand years. Now if you got really fast computers, and optimized the code you might be able to cut the problem down by a factor of 10 or even a 100, and if you got a hundred computers to all work on the problem together you might be able to generate all possible edges in a year. But that is only the first step.

You still have to sort through that list of a 100 qunitillion edges to find a complete, unique set. That's going be even worse. And then you still only have the outside edge of the puzzle. This is not the way to go.