No easy puzzles: Hardness results for jigsaw puzzles

We show that solving (bounded-degree) jigsaw puzzles requires Theta(n(2)) edge matching comparisons both in the worst case and in expectation, making all jigsaw puzzles as hard to solve as the trivial upper bound. This result applies to bounded-degree puzzles of all shapes, whether pictorial or apictorial. For non-bounded degree puzzles, we show that Omega(n logn) is a tight bound. (C) 2015 Elsevier B.V. All rights reserved.