A global approach to automatic solution of jigsaw puzzles

We present a new algorithm for automatically solving jigsaw puzzles by shape alone. The algorithm can solve more difficult puzzles than could be solved before, without the use of backtracking or branch-and-bound. The algorithm can handle puzzles in which pieces border more than four neighbors, and puzzles with as many as 200 pieces. Our overall strategy follows that of previous algorithms but applies a number of new ideas, such as robust fiducial points, "highest-confidence-first" search, and frequent global reoptimization of partial solutions. (C) 2004 Elsevier B.V. All rights reserved.