Name
Abstract | ||
|---|---|---|
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m \times 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.FUN.2021.1 | FUN |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adler Aviv | 1 | 0 | 0.34 |
| Jeffrey Bosboom | 2 | 117 | 7.70 |
| Erik D. Demaine | 3 | 4624 | 388.59 |
| Martin L. Demaine | 4 | 592 | 84.37 |
| Liu Quanquan C. | 5 | 0 | 0.34 |
| Jayson Lynch | 6 | 7 | 11.97 |