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 条
  • [21] An NP-complete fragment of fibring logic
    Wu, Yin
    Jiang, Min
    Huang, Zhongqiang
    Chao, Fei
    Zhou, Changle
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2015, 75 (3-4) : 391 - 417
  • [22] The transposition median problem is NP-complete
    Bader, Martin
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (12-14) : 1099 - 1110
  • [23] Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105 (08)
  • [24] Sublinear P system solutions to NP-complete problems
    Dinneen, Michael J.
    Henderson, Alec
    Nicolescu, Radu
    THEORETICAL COMPUTER SCIENCE, 2023, 958
  • [25] Minimum Manhattan Network is NP-Complete
    Chin, Francis Y. L.
    Guo, Zeyu
    Sun, He
    PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, : 393 - 402
  • [26] On unapproximable versions of NP-complete problems
    Zuckerman, D
    SIAM JOURNAL ON COMPUTING, 1996, 25 (06) : 1293 - 1304
  • [27] Zen Puzzle Garden is NP-complete
    Houston, Robin
    White, Joseph
    Amos, Martyn
    INFORMATION PROCESSING LETTERS, 2012, 112 (03) : 106 - 108
  • [28] Searching for capacity factors is NP-complete
    Li, Yuan
    Huang, Zheng
    Wang, Xin
    Kan, Haibin
    2008 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, PROCEEDINGS, VOLS 1-13, 2008, : 1431 - 1435
  • [29] Computing quantum discord is NP-complete
    Huang, Yichen
    NEW JOURNAL OF PHYSICS, 2014, 16
  • [30] The Cophylogeny Reconstruction Problem Is NP-Complete
    Ovadia, Y.
    Fielder, D.
    Conow, C.
    Libeskind-Hadas, R.
    JOURNAL OF COMPUTATIONAL BIOLOGY, 2011, 18 (01) : 59 - 65
12345