Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
DOI10.1007/S00373-007-0713-4zbMATH Open1123.05027OpenAlexW1992101337MaRDI QIDQ2373445FDOQ2373445
Authors: Erik D. Demaine, Martin L. 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
Recommendations
- Approximability of Edge Matching Puzzles
- On the exact complexity of polyomino packing
- On the exact complexity of polyomino packing
- Puzzles and polytope isomorphisms
- Solving jigsaw puzzles by the graph connection Laplacian
- A global approach for solving edge-matching puzzles
- scientific article; zbMATH DE number 687006
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
Cites Work
- Title not available (Why is that?)
- Simple perfect squared square of lowest order
- Title not available (Why is that?)
- On packing squares with equal squares
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The undecidability of the domino problem
- Hard tiling problems with simple tiles
- The dissection of rectangles into squares
- Average Case Complete Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Backtrack programming techniques
- Packing unit squares in squares: A survey and new results
- Online square and cube packing
- On the dissection of rectangles into right-angled isosceles triangles
- A global approach to automatic solution of jigsaw puzzles
- Squaring the Square
- The optimality of a certain purely recursive dissection for a sequentially \(n\)-divisible square
- The Quest of the Perfect Square
Cited In (32)
- A global approach for solving edge-matching puzzles
- Symmetric assembly puzzles are hard, beyond a few pieces
- Comprehensive survey of the solving puzzle problems
- Hierarchical fragmented image reassembly using a bundle-of-superpixel representation
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- No easy puzzles: hardness results for jigsaw puzzles
- Irregular polyomino tiling via integer programming with application in phased array antenna design
- Wooden Geometric Puzzles: Design and Hardness Proofs
- Games, Puzzles and Treewidth
- Hard and easy instances of L-tromino tilings
- On the exact complexity of polyomino packing
- On the exact complexity of polyomino packing
- A guide-and-observe hyper-heuristic approach to the Eternity II puzzle
- Approximability of Edge Matching Puzzles
- Small polyomino packing
- A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
- A guide-and-observe hyper-heuristic approach to the Eternity II puzzle
- Wooden geometric puzzles: Design and hardness proofs
- An integer linear programming approach to solving the Eternity puzzle
- Mathematical characterizations and computational complexity of anti-slide puzzles
- Computational complexity of cast puzzles
- Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles
- Dissection with the fewest pieces is hard, even to approximate
- Edge-matching problems with rotations
- HIROIMONO Is NP-Complete
- Rectangle packing with additional restrictions
- Variations on instant insanity
- Computational complexity of puzzles and related topics
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- Spherical quadratic equations in free metabelian groups.
- Symmetric assembly puzzles are hard, beyond a few pieces
- Solving jigsaw puzzles by the graph connection Laplacian
This page was built for publication: Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373445)
