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
相关论文
共 50 条
  • [1] Chained Block is NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2024, E107D (03) : 320 - 324
  • [2] Rikudo is NP-complete
    Viet-Ha Nguyen
    Perrot, Kevin
    THEORETICAL COMPUTER SCIENCE, 2022, 910 : 34 - 47
  • [3] BoxOff is NP-Complete
    Hayward, Ryan
    Hearn, Robert
    Jamshidian, Mahya
    ADVANCES IN COMPUTER GAMES, ACG 2021, 2022, 13262 : 118 - 127
  • [4] Five Cells and Tilepaint are NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2022, E105D (03) : 508 - 516
  • [5] Calculation Solitaire is NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2023, E106D (03) : 328 - 332
  • [6] Generalized Pyramid is NP-Complete
    Iwamoto, Chuzo
    Matsui, Yuta
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (11) : 2462 - 2465
  • [7] DECIDING FRATTINI IS NP-COMPLETE
    RYTER, CH
    SCHMID, J
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (03): : 257 - 279
  • [8] MaxCut on permutation graphs is NP-complete
    de Figueiredo, Celina M. H.
    de Melo, Alexsander A.
    Oliveira, Fabiano S.
    Silva, Ana
    JOURNAL OF GRAPH THEORY, 2023, 104 (01) : 5 - 16
  • [9] Medical diagnosis and treatment is NP-complete
    Arle, Jeffrey. E.
    Carlson, Kristen W.
    JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 2021, 33 (02) : 297 - 312
  • [10] Column subset selection is NP-complete
    Shitov, Yaroslav
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 610 : 52 - 58
12345