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.

BibTeX

@InProceedings{Tatamibari_FUN2020,
  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     = {Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020)},
  bookurl       = {https://sites.google.com/view/fun2020/home},
  MONTH         = {September 28--30},
  YEAR          = 2020,
  ADDRESS       = {La Maddalena, Italy},
  PAGES         = {1:1--1:24},

  withstudent   = 1,
  webpages      = {fonts/tatamibari},
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2021.1},
  dblp          = {https://dblp.org/rec/conf/fun/AdlerBDDLL21},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2003.08331">arXiv:2003.08331</A>, and from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2021.1">LIPIcs</A>.},
}

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, and from LIPIcs.

Availability:

The paper is available in PDF (1226k).

See information on file formats.

[Google Scholar search]

Related webpages:

Tatamibari Font