No easy puzzles: Hardness results for jigsaw puzzles

•We model jigsaw puzzle solving and study the number of edge matchings required.•Realistic jigsaw puzzles require Θ(n2)Θ(n2) comparisons in the worst case.•Realistic jigsaw puzzles require Θ(n2)Θ(n2) comparisons on average.•Generalised puzzles require (tightly) O(n2)O(n2) and Ω(nlog⁡n)Ω(nlog⁡n) comparisons.

We show that solving (bounded-degree) jigsaw puzzles requires Θ(n2)Θ(n2) 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 Ω(nlog⁡n)Ω(nlog⁡n) is a tight bound.