论文标题
双巧克力是NP完整的
Double Choco is NP-complete
论文作者
论文摘要
在尼古拉铅笔和纸游戏双巧克力中，一个难题由一个白色或灰色的单元格的M $ \ times $ n网格组成，被虚线隔开，每个单元都可能包含一个整数。目的是通过在虚线上绘制实线来将网格划分为块，在该线条上，每个块都必须包含一对具有相同形式（尺寸和形状）的白色和灰色细胞区域。整数指示该颜色中该颜色的单元格数。一个块可以包含带有整数的任何数量的单元格。我们证明了这个难题的NP完整，建立了2年的尼古拉差距。
In the Nikoli pencil-and-paper game Double Choco, a puzzle consists of an m $\times$ n grid of cells of white or gray color, separated by dotted lines where each cell possibly contains an integer. The goal is to partition the grid into blocks by drawing solid lines over the dotted lines, where every block must contain a pair of areas of white and gray cells having the same form (size and shape). An integer indicates the number of cells of that color in the block. A block can contain any number of cells with the integer. We prove this puzzle NP-complete, establishing a Nikoli gap of 2 years.
