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 条
  • [41] The 2-Attractor Problem Is NP-Complete
    Fuchs, Janosch
    Whittington, Philip
    41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024, 2024, 289
  • [42] Automatically Solving NP-Complete Problems on a Quantum Computer
    Hu, Shaohan
    Liu, Peng
    Chen, Chun-Fu
    Pistoia, Marco
    PROCEEDINGS 2018 IEEE/ACM 40TH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING - COMPANION (ICSE-COMPANION, 2018, : 258 - 259
  • [43] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS
    BAKER, BS
    JOURNAL OF THE ACM, 1994, 41 (01) : 153 - 180
  • [44] Packing cubes into a cube is NP-complete in the strong sense
    Yiping Lu
    Danny Z. Chen
    Jianzhong Cha
    Journal of Combinatorial Optimization, 2015, 29 : 197 - 215
  • [45] The minimal logically-defined NP-complete problem
    Barbanchon, R
    Grandjean, E
    STACS 2004, PROCEEDINGS, 2004, 2996 : 338 - 349
  • [46] Survey of polynomial transformations between NP-complete problems
    Ruiz-Vanoye, Jorge A.
    Perez-Ortega, Joaquin
    Pazos R, Rodolfo A.
    Diaz-Parra, Ocotlan
    Frausto-Solis, Juan
    Fraire Huacuja, Hector J.
    Cruz-Reyes, Laura
    Martinez F, Jose A.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2011, 235 (16) : 4851 - 4865
  • [47] An optical fiber network oracle for NP-complete problems
    Kan Wu
    Javier García de Abajo
    Cesare Soci
    Perry Ping Shum
    Nikolay I Zheludev
    Light: Science & Applications, 2014, 3 (2) : e147 - e147
  • [48] Two slightly-entangled NP-Complete problems
    Orús, R
    QUANTUM INFORMATION & COMPUTATION, 2005, 5 (06) : 449 - 455
  • [49] Packing cubes into a cube is NP-complete in the strong sense
    Lu, Yiping
    Chen, Danny Z.
    Cha, Jianzhong
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) : 197 - 215
  • [50] Solving NP-complete problems in the tile assembly model
    Brun, Yuriy
    THEORETICAL COMPUTER SCIENCE, 2008, 395 (01) : 31 - 46
12345