Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity

DOI10.1007/S00373-007-0713-4zbMath1123.05027OpenAlexW1992101337MaRDI QIDQ2373445

Martin L. Demaine, Erik D. Demaine

Publication date: 19 July 2007

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-007-0713-4

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50)

Related Items (23)

Small polyomino packing ⋮ Games, Puzzles and Treewidth ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ On the Exact Complexity of Polyomino Packing ⋮ An integer linear programming approach to solving the Eternity puzzle ⋮ Dissection with the Fewest Pieces is Hard, Even to Approximate ⋮ Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces ⋮ On the exact complexity of polyomino packing ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ Symmetric assembly puzzles are hard, beyond a few pieces ⋮ Rectangle packing with additional restrictions ⋮ A guide-and-observe hyper-heuristic approach to the Eternity II puzzle ⋮ Solving Jigsaw Puzzles by the Graph Connection Laplacian ⋮ A guide-and-observe hyper-heuristic approach to the Eternity II puzzle ⋮ Hierarchical fragmented image reassembly using a bundle-of-superpixel representation ⋮ Spherical quadratic equations in free metabelian groups ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ Hard and easy instances of L-tromino tilings ⋮ A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles ⋮ Edge-Matching Problems with Rotations ⋮ A Global Approach for Solving Edge-Matching Puzzles ⋮ On the hardness of solving edge matching puzzles as SAT or CSP problems ⋮ No easy puzzles: hardness results for jigsaw puzzles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On packing squares with equal squares
• Simple perfect squared square of lowest order
• Packing unit squares in squares: A survey and new results
• On the dissection of rectangles into right-angled isosceles triangles
• The optimality of a certain purely recursive dissection for a sequentially \(n\)-divisible square
• Online square and cube packing
• The dissection of rectangles into squares
• Average Case Complete Problems
• Backtrack programming techniques
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• A global approach to automatic solution of jigsaw puzzles
• The Quest of the Perfect Square
• The undecidability of the domino problem
• Squaring the Square
• Hard tiling problems with simple tiles

This page was built for publication: Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity