I was browsing around tonight, as I sometimes do, looking for interesting CS research publications, and I stumbled upon this little tidbit:

Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity

For those of you share my fascination with the Eternity II Puzzle, you’ll definitely be interested in reading this paper. In it, the author talks about the various degrees of complexity of jigsaw puzzles, polyomino packing puzzles (Eternity), and edge-matching puzzles (Eternity II).

I don’t mean to spoil the punchline or anything, but they’re all NP-complete, meaning the most successful algorithms will involve optimization, approximation, partial solutions, and problem decomposition.

Interestingly, the author also provides a proof that all three types of puzzles are trivially transformable into one another. In other words, a polyomino packing puzzle like Eternity could be logically transformed into an edge-matching puzzle like Eternity II, and the two puzzles would share the same locus of possible solutions.

Hopefully, that helps at least one of us get a little closer to the big $2 million bounty!!