“What made you decide to go to graduate school?”

During a workshop about academic careers at Allerton in 2008, Roy Yates responded to the above question in one of my favorite responses to a question of this type: “It was the most socially acceptable way to procrastinate what I wanted to do with the rest of my life.”

Recently, a friend posted on Facebook that she decided to spend time working on a jigsaw puzzle with her daughter when the ISIT 2015 submission deadline was extended. Roy responded to the thread:

I’ve been trying to understand why a puzzle with several hundred pieces is easier to put together than an ISIT paper with a few simple ideas. Each puzzle piece has several possible rotations. The ordering of the pieces would seem to explode combinatorially. You can argue that the picture provides a lot of clues, but I suspect you could do that same 200 piece puzzle upside down, without looking at the picture in a maybe one extra hour. I suppose google could tell me why, but I’d rather tag Lalitha Sankar, Chris Rose, Anand Sarwate, Krish Eswaran and Bobak Nazer.

The question immediately reminded me of a paper I’d encountered during my summer at Xerox PARC back in 2002: David Goldberg, Christopher Malon, and Marshall Bern’s “A Global Approach to Automatic Solution of Jigsaw Puzzles”. The algorithm is for the apictorial case, which corresponds to flipping over all the jigsaw pieces face-down so that the picture doesn’t help.

If one tailors an algorithm based on the picture, the discrepancy between the face-up and face-down cases could be quite severe when compared with the abstraction of Goldberg, Malon, and Bern. For instance, imagine a picture whose pixels follow an even gradient that goes from light to dark vertically and from green to red horizontally. Then by splitting the puzzle pieces by greenness and luminance, one could subdivide the initial set of puzzle pieces into four groups of one fourth the size. In fact, one could continue this subdivision until the number of pieces are small, solve them brute force, creating larger puzzle pieces that can then be solved one level above, similar to a divide-and-conquer approach like the merge sort algorithm, taking roughly steps for -piece puzzles.

The problem with the tailor-made algorithm above is that it doesn’t necessarily generalize to all pictures. One could have a picture that is symmetric, and then any sort of division would result in smaller groups that don’t necessarily merge into a single piece. Similar problems may occur if the puzzle is of a painting by Ad Reinhardt, which effectively reduces the problem to the apictorial case.

While allowances could be made, it’s worth noting that any divide-and-conquer approach cannot automatically take advantage of an algorithm like the one in Goldberg, Malon, and Bern, which attempts to solve the corners first. On the other hand and as noted in the paper, solving the corners, if abstracted in the way that the authors suggest, turns out to be equivalent to a traveling salesman problem and is NP-hard.

It’s unclear to me, however, that the traveling salesman problem is the most useful abstraction. For instance, if one assumes that puzzle pieces only fit together if they fit together in the solution, and there is a unique way in which they do, in the apictorial case, for -piece puzzles, one could test all pieces against each other pairwise in steps to create a graph based on connecting pieces (vertices) that fit together. After that, one could prune the resulting graph one vertex at a time by combining vertices that share an edge at each step, terminating in steps, thereby solving the puzzle. I suspect there is an even more efficient algorithm one could employ in this case, but this is more to illustrate how an alternate abstraction could make the problem simpler.

Ultimately, it appears there is both a sensitivity to how the jigsaw puzzle problem is abstracted as well as how useful the image is. As to whether a jigsaw puzzle is easier to solve than an ISIT paper is to write, it might be worth revisiting that in a week.