Tatamibari is NP-complete

DOI10.4230/LIPICS.FUN.2021.1MaRDI QIDQ6487564zbMATH OpenFDO

Authors Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch

Publication date 7 February 2023

zbMATH Keywords

NP-hardnessrectangle coveringNikoli puzzles

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Recommendations

• Domino tatami covering is NP-complete
• HIROIMONO Is NP-Complete
• Hashiwokakero is NP-complete
• Rikudo is NP-complete
• scientific article; zbMATH DE number 4039295
• Knuth--bendix constraint solving is NP-complete
• scientific article; zbMATH DE number 1754649
• Trahtenbrot-Zykov problem and NP-completeness
• The STO problem is NP-complete
• Shikaku and Ripple Effect are NP-complete

Cited in

(18)

• Matchstick puzzles on a grid
• LaserTank is NP-Complete
• The complexity of regex crosswords
• Rikudo is NP-complete
• Counting Islands in Nurikabe
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• Towards an algorithmic guide to Spiral Galaxies
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• Wooden geometric puzzles: Design and hardness proofs
• Domino tatami covering is NP-complete
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Wooden Geometric Puzzles: Design and Hardness Proofs
• Computational complexity of NURIKABE
• Rectangular spiral galaxies are still hard
• Computational complexity of puzzles and related topics
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• Herugolf and Makaro are NP-complete
• Shikaku and Ripple Effect are NP-complete

This page was built for publication: Tatamibari is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487564)