论文标题
tatamibari是NP完整的
Tatamibari is NP-complete
论文作者
论文摘要
在Nikoli铅笔和纸游戏Tatamibari中，一个难题由一个$ m \ times n $ 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.
