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 条
  • [31] An NP-complete fragment of fibring logic
    Yin Wu
    Min Jiang
    Zhongqiang Huang
    Fei Chao
    Changle Zhou
    Annals of Mathematics and Artificial Intelligence, 2015, 75 : 391 - 417
  • [32] The Bandwidth Allocation Problem in the ATM network model is NP-complete
    Vedantham, S
    Iyengar, SS
    INFORMATION PROCESSING LETTERS, 1998, 65 (04) : 179 - 182
  • [33] Timed protocol insecurity problem is NP-complete
    Benerecetti, Massimo
    Peron, Adriano
    FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2013, 29 (03): : 843 - 862
  • [34] Quantum advantage in deciding NP-complete problems
    Nagy, Marius
    Nagy, Naya
    QUANTUM INFORMATION PROCESSING, 2023, 22 (03)
  • [35] Quantum advantage in deciding NP-complete problems
    Marius Nagy
    Naya Nagy
    Quantum Information Processing, 22
  • [36] Broadcasting with the least energy is an NP-complete problem
    Yang, Wuu
    Tseng, Huei-Ru
    Jan, Rong-Hong
    Shen, Bor-Yeh
    MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS, 2008, : 197 - 200
  • [37] Maximizing edge-ratio is NP-complete
    Noble, Steven D.
    Hansen, Pierre
    Mladenovic, Nenad
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (18) : 2276 - 2280
  • [38] THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE FOR BIPARTITE GRAPHS
    LAI, TH
    WEI, SS
    INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 21 - 26
  • [39] Parametric runtime verification is NP-complete and coNP-complete
    Chen, Zhe
    INFORMATION PROCESSING LETTERS, 2017, 123 : 14 - 20
  • [40] Monadic logical definability of NP-complete problems
    Grandjean, E
    Olive, F
    COMPUTER SCIENCE LOGIC, 1995, 933 : 190 - 204
12345