MIT Puzzle Research
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!!
June 6th, 2007 at 12:24 pm
Thanks for the excellent link … you should come join the discussion at http://games.groups.yahoo.com/group/eternity_two/.
June 21st, 2007 at 1:09 pm
Hey Benji, long time :)
Not quite in the realm of search-spaces & NP-complete problems, but here’s an interesting CS research link you may find interesting:
http://www.dspguide.com/
The thrust of it is showing how to use various analysis techniques on signals and images. The book is free (unless you want a hardcopy), and each chapter can be downloaded if it interests you. Chapters ~2-5 are rather dry (#1 is an intro), but they’re readable if you want a refresher on stats and other mathy stuff used in the book. The stuff I found most interesting starts around chapter 24, and the chapters before it that introduce material used in 24. They start to show how the convolution and fourier analysis can be used to compare two similar images to see how closely their major features resemble eachother.
Later on in the book they also start to go into how the Z-transform (the discrete version of the laplace transform) can be used in signal analysis as well. There’s also a chapter on neural networks (yay!).
Anyway, you should hop on IM sometime and tell me how things are going in Boston :)