Eternity II

I've been interested in this puzzle for a while. It's a 16x16 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 ~10⁶⁰⁰.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? :DWell there's only 68 days remaining to solve the puzzle if you want to win the $2m prize!