2022/03/05 by Dragoljub Đurić, Đurić, Dragoljub
Computer Science · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2203.02815
openalex publication_date 2022/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Nikoli pencil-and-paper game Double Choco, a puzzle consists of an m × 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.