Open AccessJigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
Author(s) -
Erik D. Demaine,
Martin L. Demaine
Publication year - 2007
Publication title -
graphs and combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.59
H-Index - 40
eISSN - 1435-5914
pISSN - 0911-0119
DOI - 10.1007/s00373-007-0713-4
Subject(s) - polyomino , jigsaw , combinatorics , mathematics , matching (statistics) , enhanced data rates for gsm evolution , type (biology) , discrete mathematics , computer science , regular polygon , artificial intelligence , geometry , mathematics education , statistics , ecology , biology
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom