On the hardness of solving edge matching puzzles as SAT or CSP problems

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

zbMATH Keywords

puzzlesphase transitionCSPconstraintshardnessSATedge matching puzzles

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

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

• MiniSat
• MINION

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