No Easy Puzzles: A Hardness Result for Jigsaw Puzzles

摘要

We show that solving jigsaw puzzles requires Θ(n~2) edge matching comparisons, making them as hard as their trivial upper bound. This result generalises to puzzles of all shapes, and is applicable to both pictorial and apictorial puzzles.