Tatamibari is NP-complete
From MaRDI portal
Publication:6487564
DOI10.4230/LIPICS.FUN.2021.1zbMATH Open1515.68147MaRDI QIDQ6487564FDOQ6487564
Authors: Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch 
Publication date: 7 February 2023
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)
Cited In (18)
- Computational complexity of NURIKABE
- Shikaku and Ripple Effect are NP-complete
- Matchstick puzzles on a grid
- Rikudo is NP-complete
- Towards an algorithmic guide to Spiral Galaxies
- The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
- Wooden Geometric Puzzles: Design and Hardness Proofs
- Counting Islands in Nurikabe
- LaserTank is NP-Complete
- Herugolf and Makaro are NP-complete
- Wooden geometric puzzles: Design and hardness proofs
- The complexity of regex crosswords
- Rectangular spiral galaxies are still hard
- Domino tatami covering is NP-complete
- NP-completeness of two pencil puzzles: Yajilin and Country Road
- Computational complexity of puzzles and related topics
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
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)
