Tatamibari is NP-complete

Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch

TL;DR

This paper proves that the Japanese logic puzzle Tatamibari is NP-complete, a significant result that took 16 years to establish since the puzzle's introduction. The authors introduce a novel "gadget area hardness framework" to tackle this and similar area-coverage puzzles, demonstrating its applicability to existing NP-hardness proofs.

What Problem Does This Paper Address?

The paper tackles the computational complexity of Tatamibari, a popular pencil-and-paper logic puzzle published by Nikoli. For decades, computer scientists have been analyzing the complexity of these puzzles, with many being proven NP-complete. The authors introduce the concept of the "Nikoli gap," the time between a puzzle's release and its NP-hardness proof. Tatamibari, released in 2004, had a gap of 16 years, making its NP-completeness a long-standing open question. The paper aims to close this gap and, in doing so, provides a general framework for analyzing the complexity of a class of puzzles.

Methods

The core of the paper is the introduction of a "gadget area hardness framework." This framework allows researchers to prove the NP-hardness of puzzles by breaking them down into smaller, reusable components called "gadgets." These gadgets are subpuzzles with specific properties related to how their areas can be covered. The framework involves:

  • Defining Gadgets: Creating modular puzzle components (like wires, variables, and clauses) that represent logical operations.
  • Profile Tables: Characterizing the valid ways these gadgets can be solved (their "profiles") and proving that these tables are "proper" (only contain valid solutions) and "complete" (all other possibilities are locally impossible).
  • Composition Algorithm: Showing how these gadgets can be combined to form a larger puzzle instance that mirrors a known NP-hard problem (in this case, planar rectilinear monotone 3SAT).
  • Reduction: Demonstrating that a solution to the Tatamibari puzzle instance corresponds directly to a satisfying assignment of the 3SAT instance, and vice versa.

The authors specifically reduce from planar rectilinear monotone 3SAT, a variant of the classic 3SAT problem. They construct wire, variable, and clause gadgets that, when assembled, form a Tatamibari puzzle instance. The "filling algorithm" and "composition algorithm" are crucial for ensuring that the overall puzzle's solvability depends solely on the correct configuration of these gadgets.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity proofs and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • The "Nikoli Gap": The paper formalizes the observation that there's often a significant delay between a puzzle's popularity and its computational complexity analysis. Tatamibari's 16-year gap highlights this phenomenon.
  • Generalizable Gadget Framework: The most significant contribution is the "gadget area hardness framework." This provides a systematic way to prove NP-hardness for a broad class of area-coverage puzzles, moving beyond ad-hoc reductions.
  • Tatamibari's NP-Completeness: The paper definitively proves that Tatamibari is NP-complete, settling a long-standing question and adding it to the growing list of NP-complete logic puzzles.
  • Mathematical Puzzle Font: The authors introduce a novel "Tatamibari font" where each letter of the alphabet is represented by a unique Tatamibari puzzle whose solution forms the letter. This is a creative application of puzzle design.
  • The Four-Corner Constraint: The paper emphasizes the crucial role of the "no four rectangles share a corner" constraint in the NP-hardness proof, suggesting it's a key element for constructing hard instances.

Key Results

  • Tatamibari is NP-complete: The paper proves that Tatamibari is NP-complete.
  • 16-Year Nikoli Gap: This result establishes a 16-year Nikoli gap for Tatamibari.
  • Gadget Area Hardness Framework: A novel framework for proving NP-hardness of area-coverage puzzles is introduced and demonstrated.
  • Framework Applicability: The paper shows that this framework can be used to re-analyze existing NP-hardness proofs, such as for Spiral Galaxies.
  • Tatamibari Font: A functional font for encoding text using Tatamibari puzzles is presented.

Limitations and Future Work

  • Solver Limitations: The authors note that their Z3-based solver can only verify the correctness of constant-size gadgets, while the reduction requires gadgets that telescope to arbitrary widths. This necessitates manual proofs of correctness for these variable-width gadgets.
  • Open Problems: The authors pose several open questions:
  • Is Tatamibari ASP-hard (determining if a puzzle has more than one solution)?
  • Is Tatamibari #P-hard (counting the number of solutions)?
  • Are restricted versions of Tatamibari (e.g., only '+' clues, or without the four-corner constraint) still hard?
  • Parsimonious Reduction: The current reduction is not parsimonious, meaning it might not preserve the number of solutions. Reworking the gadgets and filler would be needed to address this for counting problems.

Summary updated

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.
BibTeX
@inproceedings{adler2020tatamibari,
  author = {Aviv Adler and Jeffrey Bosboom and Erik D. Demaine and Martin L. Demaine and Quanquan C. Liu and Jayson Lynch},
  title = {{Tatamibari is NP-complete}},
  booktitle = {DSpace@MIT},
  year = {2020},
}
Figure