Jigsaw puzzle fun


From "Wonderful Life" by Stephen Jay Gould. (I anticipated the punchline, by the way, then got a sick little lurch to see it confirmed.)

I once spent a week in the field with Richard Leakey, and I could sense both his frustration and pride that his wike Meave and their coworker Alan Walker could take tiny fragments of bone and, like a three-dimensional jigsaw puzzle, put together a skull, while he could do the work only imperfectly (and I saw nothing at all but fragments in a box). Both Meave and Alan showed these skills from an early age, largely through a passion for jigsaw puzzles (curiously, both, as children, liked to do puzzles upside down, working by shapes alone, with no help from the picture).

Hmm. Jigsaw puzzles being fun. How could we model this?

Define a cost function that increases monotonically with the mismatch at each edge. What kind of cost function? Add the square of the amount of mismatch at each edge point, or perhaps add something a little less harsh. The choice will change the location and number of local minima in the cost landscape. Maybe for your application close enough is good enough, in which case go for a softer cost function. Or maybe it isn't, in which case go for the harsh cost function.

With the harsh cost function, the true solution will tend to beat anything else hands down. Very satisfying to find. Fun. With a softer cost function, maybe the true solution won't be much better than some slightly less good ones. No great satisfaction, not so fun maybe.