Intellectual Exercise

Partial Solution to Eternity 2 Puzzle

A while back I spent some time on the Eternity 2 puzzle. It soon became obvious that a computerized, brute force approach was unlikely to find a solution before our sun goes Nova. As I didn't have any other big ideas I let it slide. Occasionally I will get an email notifying me of some activity in the Yahoo group dedicated to this proposition. Usually they are cryptic files with the results of how another idea failed. This morning though I got several images of partial solutions. The above image is only ten tiles square, the original puzzle has sixteen tiles on a side. Also, all the tiles around the edge of the image are missing one edge (the gray triangles) and the half-tile in the upper left corner doesn't match. Still, it's impressive. And pretty.

Introduction To Solid State Physics by Charles Kittel

On another tangent I joined a local Meetup group to talk about physics. I went to a couple of meetings but I haven't been back. It takes an hour to go to Portland and back during which my monster big rig sucked down two or three gallons of gas, and this was back when gas was $4 a gallon, so my wallet noticed.
    Anyway I got an email a couple of days ago talking about elementary physics textbooks:

Solid State Physics by R J Singh

Introduction to Solid State Physics by Charles Kittel

Kittel's book got a rave review in the email, and it came with a link where I might be able to get a really cheap copy, so I followed the link to AddALL books, which led me to AbeBooks, where I did buy a copy for under $20, including shipping. The curious thing here is that AbeBooks is in India and evidently they have figured out how Hong Kong is shipping stuff to the USA cheaply because the shipping was under $5. I'm a little curious to see how long it will take, and I admit I am a little excited about getting something from half way around the world. I have great intentions of reading it. We shall see how that pans out.

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.

Eternity Puzzle, Part 6

I figured out what the problem was with my program. It's a matter of how you look at orientation. If your point of reference moves clockwise, that is the same as the having the reference remain still and the tile turn counter-clockwise. I still haven't fixed the code. I don't seem to have the necessary motivation. But I came up with a new scheme that might lead to a solution. I had great hopes of implementing it, but since that isn't happening, I thought I would write it up and maybe some industrious person could make use of it.

The idea is to start small, but pervasive, and work your way up. Start with making square blocks of four tiles whose adjoining edges match. Start with the first tile and make as many blocks of four as you can. Go to the next tile and repeat. You will have a couple hundred groups of four for each tile.

Next, go through the list and eliminate any duplicates. Now select 64 of the blocks such that each tile is used only once. See if the number of unmatched edges can be arranged so that the counts in each direction come out even. That is, for any one color/pattern, the number of edges facing left should equal the number of edges facing right, and the number of edges facing down should equal the number of edges facing up. If this set meets all these criteria, then you can go on to the next phase.

At this point there are two directions you can go. One is to generate all the possible sets of blocks that meet these criteria. The other is go on to the next phase.

The next phase is to take four of your blocks and see if you can group them into square blocks of 16 tiles. Since we have already established the orientations of the 4 tile blocks, this should be fairly quick to complete, or fail.

When you have reached this point then it might be worthwhile to just see if you can solve the complete puzzle. You only have 16 squares at this point.

The only problem I see is that the number of combinations of 4 tile blocks might be too enormous to winnow down in a timely manner. The other problem is that there are a number of steps where it is necessary to insure that all possibilities are considered. A brute force approach where you only check one tile at a time does not have this weakness.

De Bug

I'm still playing with the Eternity II puzzle. I came up with a couple of ideas that might reduce the problem to something that can be solved. Probably not, but maybe. So I've been writing some code and I got to a place where the program runs but it does not work. So I start trying to find the problem, and I cannot get a handle on it. On one hand the code is dirt simple. On the other we are dealing with rotations, and for some reason I am having a devil of a time sorting it out. Might have to go back to pencil and paper.

Eternity Puzzle, Part 5

This puzzle has about a gazillion combinations, only one of which is the correct solution, so unless you get really lucky, you are not going to solve it. The odds are worse than the lottery.

To avoid spending a bunch of money, I generated a random puzzle, and used the tiles from that as input for my solver. I figure if I can come up with a scheme to solve a random puzzle, then I might have a chance with the real puzzle. I changed the reporting scheme so now it only issues a report every 10 million tiles, which is about every three seconds.

Anyway, it's one thing to say there are a gazillion combinations, it's another thing to sit and watch this program try a billion combinations a minute and not make any progress. It's been running for a couple of days now and it hasn't gotten past the 16th tile, and there are 256 tiles in the puzzle. And it's not like it's going to suddenly start making progress. It was up to 16 tiles in the first minute. That's how far it can get before it can't find another matching tile, and it starts backing off and retrying, again and again and again ...

There are a thousand edges (256 tiles times 4 sides). There are ten colors. Ten is just an arbitrary number I picked. Each time we place a tile we have two known edges we have to match against. (We start in the corner with two known edges and then work our way up the side, over the top, then down, spiralling ever closer to the center.) One known edge cuts the number of possible tiles to 100 (1/10th of 1000), two edges cuts it down to about 10 (divide by ten again). So for each spot on the board, there are ten possible tiles. Ten million is 10^7 (ten to the seventh power). Every three seconds (ten million trials) we see the most recent seven tile id numbers change. Hmmph. Imagine that.

I should put it away now and move on to other things. We'll see how that works. There are a couple of other tricks I could try ...

Eternity Puzzle Solver: Is it working?

I've been thinking about the Eternity II puzzle, I mean $2 million would be worth putting in a little effort. I know I am not going to solve it, and I am not going to win the money, but it has sucked me in anyway and I spent the last few days working on it. I did some thinking, and then I wrote some code, and then I realized I didn't really know what I was doing, so I thought about it some more, and Sunday morning I woke up early and wrote down my plan (in English). Then I sat down to write the code, there were a couple of hiccups, but I got those squared away and I fired it up yesterday evening. It got through the first column without any trouble, but once it got to the top edge it seemed to get stuck. It's been running the better part of a day and it's still stuck on the top row. So is there a bug in the program that is making it try the same tile over and over again, or is just really taking that long? I went through the program again, and rearranged some of the code, but I didn't find anything that could have been causing a real problem. Given the kind of problem, it could very well be taking that long. I mean it will take an eternity to get the complete solution, so what's a few hours or days to complete one row?

I suppose what I need it some kind of stop command that would allow me to stop the program and examine the results so far, and is satisfactory let it resume. This is going to take some finagling. Probably have to use some POSIX calls or something.

Eternity II, Part 3

I couldn't leave it alone until I sorted it out. Here's the formula for calculating the possible number of unique square tiles where each edge can be a different color and N is the number of colors. I have verified it up to 10 colors. Spreadsheet here.

N
+ (N * (N-1))
+ (N * (N-1) / 2)
+ (N * (N-1) / 2)
+ (N * (N-1) * (N-2))
+ (N * (N-1) * (N-2) / 2)
+ (N * (N-1) * (N-2) * (N-3) / 4)

While I was fooling around with this I ran into a weird problem. When I tried to reduce the formula through factoring, the computer code would not produce the right number for all the different values of N. It would get most of them right, but not all. I am going to try and stop fooling with this now and go on to something else. We shall see how that works. Here is the formula that does not work:

N * (1 + ((N-1) * (2 + ((N-2) * (1.5 + (N-3)/4)))))

Update: problem was caused by intermediate results being fractions. Changing N to a floating point number fixed the problem.

Eternity II, Part 2

I was thinking about this puzzle the other day ($2 million in prize money is kind of attention getting), and I got to wondering how many different colors/edge patterns you would need in order for all pieces to be different. (The pieces are all square tiles, each edge can be a different color/pattern.) If you have only one color, then there is only one possible pattern: all pieces would be the same. If you used two colors, you could have 16 possible patterns (16 = 2 x 2 x 2 x 2), but rotating pieces will show that some are duplicates of each other. After that it gets complicated, so I wrote a little program to count up the possible patterns and eliminate all the duplicates. The results are in the "picture".

I am thinking there has to be a better way to calculate the number of unique pieces, but I'll be durned if I know what it is. I'll bet Stu knows, or maybe Jack.

Update January 2017 replaced missing image.

Eternity II Puzzle

I've been looking at the Eternity II puzzle. It's interesting from a programming point of view. I have a couple of ideas that might make it possible to find a solution (before the sun burns out), but unless I spend some more time investigating, I won't know. More investigating requires buying a copy of the puzzle (for $130!), as it seems no one has had the nerve to post what all the pieces look like. And then I'm afraid that after I investigated I would realize that all my ideas are for nought and it will still take from now until forever before anyone finds a solution. So why bother? Well, it might be a good application for CUDA, or a test of a quantum computer.

At least one enterprising soul is promoting a distributed solution, à la Protein Folding or SETI. Sign your computer up to work on the puzzle and if it happens to find the answer, the program's creator will split the prize with you.