Paper by Erik D. Demaine

Reference:
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch, “Tatamibari is NP-complete”, in Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), La Maddalena, Italy, September 28–30, 2020, 1:1–1:24.

Abstract:
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.

Comments:
This paper is also available as arXiv:2003.08331.

Availability:
The paper is available in PDF (1226k).
See information on file formats.
[Google Scholar search]

Related webpages:
Tatamibari Font


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated August 3, 2020 by Erik Demaine.