Search Time when Solving Random Jigsaw Puzzles with a Planted Solution

John Tsotsos asked his AI students to work on having an AI solve a jigsaw puzzle, though it is NP-complete. This paper considers the search time of the recursive backtracking algorithm for solving it when the puzzle pieces are generated randomly with a planted solution. Feeling that a jigsaw puzzle should have a particular image when completed, we set the probability that two pieces fit together locally to be just small enough that with high probability the planted solution is unique. We were surprised to see that in this case the recursive backtracking algorithm which expands a rectangle from a corner has expected 1 + ǫ branching width. In contrast, this width is exponential if it attempts to put together just the edge pieces into a frame, build a triangle from a corner, or build a block in the middle. If the probability of pieces fitting together is increased just to the point that there is an exponential number of complete solutions, then no matter which order the pieces are put together it takes an exponential amount of time to find one of these exponentially many solutions. It is also interesting that for the different orders of completing the puzzle, there are very different “reasons ” for the exponential blowup. We coded the algorithm and it ran just as described