Tatamibari is NP-complete
Tatamibari is NP-complete
复制标题
Tatamibari 是 NP 完全的
DOI：
10.4230/lipics.fun.2021.1
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
J. Lynch
中科院分区：
文献类型：
--
作者：
Aviv Adler;Jeffrey Bosboom;E. Demaine;M. Demaine;Quanquan C. Liu;J. Lynch
在Nikoli的纸与纸的游戏Tatamibari中，一个谜题由$m \times n$网格的单元格组成，每个单元格可能包含+，-，|.目标是将网格划分为不相交的矩形，其中每个矩形只包含一个线索，包含+的矩形是正方形，包含-的矩形严格地水平比垂直长，包含|垂直长度严格大于水平长度，并且没有四个矩形共用一个角。我们证明了这个难题是NP完全的，建立了一个16年的尼古拉差距。沿着的方式，我们介绍了一个小工具框架，用于证明硬度类似的难题，涉及面积覆盖，并表明它适用于现有的NP-硬度证明螺旋镀锌。我们还提出了一个数学拼图字体的Tatamibari。
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.