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

DOI10.1007/s00373-007-0713-4zbMath1123.05027MaRDI 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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

52C20: Tilings in (2) dimensions (aspects of discrete geometry)

05B40: Combinatorial aspects of packing and covering

05B50: Polyominoes

Related Items

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

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