Pith. sign in

Tatamibari is NP-complete

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

citation-role summary

background 1

citation-polarity summary

fields

cs.CC 1

years

2025 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

Linear Planar 3-SAT and Its Applications in Planning

cs.CC · 2025-06-17 · conditional · novelty 7.0

Linear Planar 3-SAT is NP-complete, its reconfiguration is PSPACE-complete, and these results imply NP-completeness of bounded 2D connected multi-agent pathfinding and PSPACE-completeness of the unbounded version.

citing papers explorer

Showing 1 of 1 citing paper.

  • Linear Planar 3-SAT and Its Applications in Planning cs.CC · 2025-06-17 · conditional · none · ref 7 · internal anchor

    Linear Planar 3-SAT is NP-complete, its reconfiguration is PSPACE-complete, and these results imply NP-completeness of bounded 2D connected multi-agent pathfinding and PSPACE-completeness of the unbounded version.