# Tatamibari is NP-complete

arXiv: https://arxiv.org/abs/2003.08331 · HTML: https://mlsanity.com/paper/2003.08331/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [Finding hardness reductions automatically using SAT solvers](https://mlsanity.com/paper/2402.06397/) (2024)

## Abstract (arXiv)

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.