Five Cells and Tilepaint are NP-Complete

被引：5
|
作者：
Iwamoto, Chuzo [1 ]
Ide, Tatsuya [1 ]
机构：
[1] Hiroshima Univ, Grad Sch Adv Sci & Engn, Higashihiroshima 7398527, Japan
来源：
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2022年 / E105D卷 / 03期
关键词：
Five Cells; Tilepaint; pencil puzzle; NP-complete; COMPUTATIONAL-COMPLEXITY;
D O I：
10.1587/transinf.2021FCP0001
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
引用
收藏
页码：508 / 516
页数：9
相关论文
共 50 条
  • [1] Generalized Pyramid is NP-Complete
    Iwamoto, Chuzo
    Matsui, Yuta
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (11) : 2462 - 2465
  • [2] Chained Block is NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2024, E107D (03) : 320 - 324
  • [3] Choco Banana is NP-Complete∗
    Iwamoto, Chuzo
    Tokunaga, Takeru
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2024, E107A (09) : 1488 - 1491
  • [4] Hashiwokakero is NP-complete
    Andersson, Daniel
    INFORMATION PROCESSING LETTERS, 2009, 109 (19) : 1145 - 1146
  • [5] Rikudo is NP-complete
    Viet-Ha Nguyen
    Perrot, Kevin
    THEORETICAL COMPUTER SCIENCE, 2022, 910 : 34 - 47
  • [6] TETRAVEX is NP-complete
    Takenaga, Yasuhiko
    Walsh, Toby
    INFORMATION PROCESSING LETTERS, 2006, 99 (05) : 171 - 174
  • [7] BoxOff is NP-Complete
    Hayward, Ryan
    Hearn, Robert
    Jamshidian, Mahya
    ADVANCES IN COMPUTER GAMES, ACG 2021, 2022, 13262 : 118 - 127
  • [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] Moon-or-Sun, Nagareru, and Nurimeizu are NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105A (09) : 1187 - 1194
12345