Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
From MaRDI portal
Publication:2373445
DOI10.1007/s00373-007-0713-4zbMath1123.05027MaRDI QIDQ2373445
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
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
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, Irregular polyomino tiling via integer programming with application in phased array antenna design, Rectangle packing with additional restrictions, On the hardness of solving edge matching puzzles as SAT or CSP problems, No easy puzzles: hardness results for jigsaw puzzles, Spherical quadratic equations in free metabelian groups, Edge-Matching Problems with Rotations
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
