Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity

摘要

We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.