2026-07-24T02:02:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12762 2024-03-06T10:49:07Z ddc:004 open_access

Tatamibari Is NP-Complete Adler, Aviv Bosboom, Jeffrey Demaine, Erik D. Demaine, Martin L. Liu, Quanquan C. Lynch, Jayson Nikoli puzzles NP-hardness rectangle covering In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m x 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aviv Adler and Jeffrey Bosboom and Erik D. Demaine and Martin L. Demaine and Quanquan C. Liu and Jayson Lynch 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.1 urn:nbn:de:0030-drops-127624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.1 eng https://creativecommons.org/licenses/by/3.0/legalcode