Choco Banana is NP-Complete∗

被引：0

作者：

Iwamoto, Chuzo ^{[1
]}

Tokunaga, Takeru ^{[2
]}

机构：

[1] Hiroshima Univ, Grad Sch Adv Sci & Engn, Higashihiroshima 7398521, Japan

[2] Hiroshima Univ, Sch Informat & Data Sci, 739-8527, Higashihiroshimashi 7398527, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2024年 / E107A卷 / 09期

关键词：

Choco Banana; pencil puzzle; NP-complete;

D O I：

10.1587/transfun.2023DML0001

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Choco Banana is one of Nikoli's pencil puzzles. We study the computational complexity of Choco Banana. It is shown that deciding whether a given instance of the Choco Banana puzzle has a solution is NP-complete.

引用

页码：1488 / 1491

页数：4