Tatamibari is NP-complete
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m × n grid of cells, where each cell possibly contains a clue among⊞, ⊟, ◫. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing are square, rectangle...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl, Leibniz Center for Informatics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129836 |
| _version_ | 1811092823108222976 |
|---|---|
| author | Adler, Aviv Bosboom, Jeffrey William Demaine, Erik D Demaine, Martin L Liu, Quanquan C. Lynch, Jayson R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Adler, Aviv Bosboom, Jeffrey William Demaine, Erik D Demaine, Martin L Liu, Quanquan C. Lynch, Jayson R. |
| author_sort | Adler, Aviv |
| collection | MIT |
| description | In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m × n grid of cells, where each cell possibly contains a clue among⊞, ⊟, ◫. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing are square, rectangles containing are strictly longer horizontally than vertically, rectangles containing ◫ are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari. |
| first_indexed | 2024-09-23T15:28:21Z |
| format | Article |
| id | mit-1721.1/129836 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:28:21Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl, Leibniz Center for Informatics |
| record_format | dspace |
| spelling | mit-1721.1/1298362022-09-29T14:45:38Z Tatamibari is NP-complete Adler, Aviv Bosboom, Jeffrey William Demaine, Erik D Demaine, Martin L Liu, Quanquan C. Lynch, Jayson R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m × n grid of cells, where each cell possibly contains a clue among⊞, ⊟, ◫. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing are square, rectangles containing are strictly longer horizontally than vertically, rectangles containing ◫ are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari. 2021-02-19T20:02:36Z 2021-02-19T20:02:36Z 2020-03 2020-12-09T18:24:36Z Article http://purl.org/eprint/type/JournalArticle 9783959771450 1868-8969 https://hdl.handle.net/1721.1/129836 Adler, Aviv et al. “Tatamibari is NP-complete.” 10th International Conference on Fun with Algorithms, May-June 2021, Favignana Island, Italy, Schloss Dagstuhl and Leibniz Center for Informatics, 2021. © 2021 The Author(s) en 10.4230/LIPIcs.FUN.2021.1 10th International Conference on Fun with Algorithms Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf Schloss Dagstuhl, Leibniz Center for Informatics DROPS |
| spellingShingle | Adler, Aviv Bosboom, Jeffrey William Demaine, Erik D Demaine, Martin L Liu, Quanquan C. Lynch, Jayson R. Tatamibari is NP-complete |
| title | Tatamibari is NP-complete |
| title_full | Tatamibari is NP-complete |
| title_fullStr | Tatamibari is NP-complete |
| title_full_unstemmed | Tatamibari is NP-complete |
| title_short | Tatamibari is NP-complete |
| title_sort | tatamibari is np complete |
| url | https://hdl.handle.net/1721.1/129836 |
| work_keys_str_mv | AT adleraviv tatamibariisnpcomplete AT bosboomjeffreywilliam tatamibariisnpcomplete AT demaineerikd tatamibariisnpcomplete AT demainemartinl tatamibariisnpcomplete AT liuquanquanc tatamibariisnpcomplete AT lynchjaysonr tatamibariisnpcomplete |