Eternity II

I’ve been interested in this puzzle for a while. It’s a 16×16 jigsaw puzzle, with each piece being split diagonally into 4 quadrants with different designs. You have to fill the jigsaw puzzle mat with the 256 pieces such that all the edges match up to ones with similar designs. Here’s a picture to give you an idea:

Yes, I did go out and buy the puzzle. It looks far more formidable in the flesh (or rather, in the cardboard).

A friend and I discussed the puzzle at length and he’s been working on a simple solver, just for fun. There are a couple of solvers already out there for this. I’ve got the edge sets worked out, and it’s fun to play around with some ideas for algorithms and solvers. The puzzle is an edge matching problem, and is NP-Complete. As such it has no ‘easy’ way of being solved. Interestingly, it falls into the same complexity class as packing puzzles, which was the idea behind Eternity I (which I also own, but I did not like as much as it was really easy to knock all the pieces out of position). Interestingly the guys who solved Eternity-1 helped design this second incarnation. Here’s a page explaining how they solved the first version.

The Wikipedia page says that the creators designed the puzzle to have a low number of exact solutions, to try and make it even harder (how rude). I read somewhere that the number of exact solutions is estimated to be ~20,000. Not a lot considering that the number of ways of placing the pieces is ~10600.

So how do you go about solving an intractable problem?

Here’s a guy who’s reviewed 2 solvers, one C++ based and one Java based (although the Java one is a port of the C++ one). There’s also a sorceforge project dedicated to this. There are also a couple of distributed computing efforts to try and solve the puzzle (essentially farming out tasks to a large network of computers, similar to the SETI@home project). Although one might ask how the prize would be fairly split in the case of such a syndicate win, especially if the participants contribute different fractions of the total computational time.

For a more technical insight into this class of puzzles, I suggest reading this paper.

I was wondering what kind of heuristics could be applied to this situation. The solvers I have seen so far all seem to be brute-force based. Surely using a simulated annealing approach in combination with some kind of random swap / GA would be better? If you could get a large proportion of the pieces fitted, say 80-90% using this approach, then you could swap to a different approach for the last part (even a brute force method). Knowing how long to anneal the system for is the tricky part. It would be interesting to define a fitness function as, say, the number of satisfied edges, and then plot this value as a function of time, to monitor the convergence rate. You could quickly get an idea of how interrupting the annealing schedule with, say, different rates of random swaps (mutations), influences the convergence rate.

The problem could also be broken into sub-problems, which can be solved in parallel. The obvious example being that of solving the fitting of the edge pieces. The edge pieces are defined by one of their quadrants being grey, and the corner pieces have 2 grey quadrants. (I wonder how much more (or less??) complex the problem would be if the edges were not defined as such, and all the pieces were of the same format?)… OK maybe I’ll think about that later…

I was also then naturally led to ponder whether or not this problem could be mapped onto a model which was compatible with quantum computer software. I.e. if a solver could be written for this specific puzzle which would benefit from a quantum speedup, using some kind of quantum annealing technique. Any takers? 😀

Well there’s only 68 days remaining to solve the puzzle if you want to win the $2m prize!

Advertisements

10 thoughts on “Eternity II

  1. rrtucci says:

    I just found this most wondrous proof of this puzzle, but I don’t have enough room in this margin to write it down.

  2. Ian Durham says:

    Wow. This is *really* neat. I need to get my hands on this. I love puzzles. A slightly different “puzzle” (actually, completely different, but still a puzzle) is Christopher Manson’s book “Maze” (which is a bit creepy and diabolical but I figured it out).

  3. rrtucci says:

    I don’t think they would dangle $2M in front of you if they expected you to solve it. What they do expect you to do is to succumb to your greedy banker instincts and buy it.

  4. physicsandcake says:

    Well I bought it because it looked like fun. I’ve pretty much got my £35 worth or whatever it cost (I think I got it at a reduced price anyway) just from the entertainment value it’s given me in thinking about it.

  5. Geordie says:

    What do you have to do to win the $2M? Is there a problem statement somewhere?

  6. Geordie says:

    Ahh got it. I suspect that the manufacturers are going to have to shell out that $2M… by the way it looks like the contest closes December 2010 so there’s a lot of time to work on it. Great promotional idea though.

  7. rrtucci says:

    Susan, since you have led me to some corker websites, here is one in return. Software at its best
    http://www.palinaspresident.us/

  8. physicsandcake says:

    @Geordie: Oh, I thought it was December 2008? – Maybe they changed it due to not having received enough entries!

    As my friend said to me, it’s a shame people have to offer large monetary incentives to get people interested in this kind of problem.

  9. More news and combinations computations here :
    http://eternity2blogger.over-blog.com/

    Regards,
    Eternity II Blogger.

  10. nobody says:

    It converges very quickly at the beginning, to have it fully solved you need 480 matching couples, I’ve found 346 matching couples in cca 100 iterations of swapping and rotating in a human driven web browser based game without flash needed :]. HUH, GO MTHRFCKRZ!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s