Link between best-fit synthesis and solving jigsaw puzzles



Consider how one might go about solving a jigsaw puzzle, such as my fractal puzzle. You keep linking pieces into the puzzle, until you reach a point where what you have is inconsistent with itself -- there is no piece that will properly join up a particular area. Then what do you do? Maybe back-track a bit, take out a few pieces. Sometimes this will work, sometimes you need to backtrack even further. It might take several iterations of backtracking and adding new pieces until you get it right.

Which pieces to remove? A good strategy might be to remove a section that is loosely connected to the rest.

So, considering a section connected to the rest of the puzzle by n join points, with what probability do you remove that particular section? Is that probability related to n or to n-squared. Does the distribution have a fat tail?

In other words, do you tear out a variety of sizes of chunks? If you tear out chunks all of around the same size you may get to a solution faster, but you might also get totally stuck. If you do tear out a variety of chunk sizes, it may take longer to solve the puzzle -- you'll sometimes throw out a huge chunk that nearly but not quite fits. But this may be the only way to solve it.

Variation: join points may have different strengths. With this addition, puzzle solving begins to look very similar to best-fit texture synthesis.

And this all, of course, links to autism: tearing out varying sizes of chunks is the autistic strategy, tearing out consistently sized chunks is the normal strategy.

A few other possible variables [Updated 4/10/04]:

These types of things might be measured by timing how long a person takes to solve a carefully designed set of jigsaw puzzles. Another way would be to look at the pattern of deletions when they edit text.