On the hardness of solving edge matching puzzles as SAT or CSP problems
From MaRDI portal
Publication:2342584
DOI10.1007/s10601-012-9128-9zbMath1310.05055OpenAlexW2046346504WikidataQ62043254 ScholiaQ62043254MaRDI QIDQ2342584
Carles Mateu, Cèsar Fernández, Ramón Béjar, Carlos Ansótegui
Publication date: 29 April 2015
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10601-012-9128-9
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
A guide-and-observe hyper-heuristic approach to the Eternity II puzzle ⋮ A guide-and-observe hyper-heuristic approach to the Eternity II puzzle
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tetravex is NP-complete
- Symmetry definitions for constraint satisfaction problems
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Theory and Applications of Satisfiability Testing
- Determining computational complexity from characteristic ‘phase transitions’
- On the Power of k-Consistency
- Theory and Applications of Satisfiability Testing
This page was built for publication: On the hardness of solving edge matching puzzles as SAT or CSP problems