BLOCKSUM is NP-Complete

被引：7
|
作者：
Haraguchi, Kazuya [1 ]
Ono, Hirotaka [2 ]
机构：
[1] Ishinomaki Senshu Univ, Fac Sci & Engn, Dept Informat Technol & Elect, Ishinomaki, Miyagi 9868580, Japan
[2] Kyushu Univ, Fac Econ, Dept Econ Engn, Fukuoka 8128581, Japan
来源：
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2013年 / E96D卷 / 03期
关键词：
NP-completeness; combinatorial puzzle; Latin square; BLOCKSUM;
D O I：
10.1587/transinf.E96.D.481
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
BLOCKSUM, also known as KEISANBLOCK in Japanese, is a Latin square filling type puzzle, such as Sudoku. In this paper, we prove that the decision problem whether a given instance of BLOCKSUM has a solution or not is NP-complete.
引用
收藏
页码：481 / 488
页数：8
相关论文
共 50 条
  • [1] Shellability is NP-complete
    Goaoc, Xavier
    Patak, Pavel
    Patakova, Zuzana
    Tancer, Martin
    Wagner, Uli
    JOURNAL OF THE ACM, 2019, 66 (03)
  • [2] TETRAVEX is NP-complete
    Takenaga, Yasuhiko
    Walsh, Toby
    INFORMATION PROCESSING LETTERS, 2006, 99 (05) : 171 - 174
  • [3] DAG reversal is NP-complete
    Naumann, Uwe
    JOURNAL OF DISCRETE ALGORITHMS, 2009, 7 (04) : 402 - 410
  • [4] Properties of NP-complete sets
    Glasser, Christian
    Pavan, A.
    Selman, Alan L.
    Sengupta, Samik
    SIAM JOURNAL ON COMPUTING, 2006, 36 (02) : 516 - 542
  • [5] System BV is NP-complete
    Kahramanogullari, Ozan
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2006, 143 : 87 - 99
  • [6] System BV is NP-complete
    Kahramanogullari, Ozan
    ANNALS OF PURE AND APPLIED LOGIC, 2008, 152 (1-3) : 107 - 121
  • [7] Autoreducibility of NP-Complete Sets
    Hitchcock, John M.
    Shafei, Hadi
    33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
  • [8] Elastic image matching is NP-complete
    Keysers, D
    Unger, W
    PATTERN RECOGNITION LETTERS, 2003, 24 (1-3) : 445 - 453
  • [9] Border Basis Detection is NP-complete
    Ananth, Prabhanjan V.
    Dukkipati, Ambedkar
    ISSAC 2011: PROCEEDINGS OF THE 36TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2011, : 11 - 18
  • [10] Universal solutions for NP-complete problems
    Portier, N
    THEORETICAL COMPUTER SCIENCE, 1998, 201 (1-2) : 137 - 150
12345