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 条
  • [21] Solvability of Peg Solitaire on Graphs is NP-Complete
    Ito, Kazushi
    Takenaga, Yasuhiko
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2023, E106D (06) : 1111 - 1116
  • [22] On universally easy classes for NP-complete problems
    Demaine, ED
    López-Ortiz, A
    Munro, JI
    THEORETICAL COMPUTER SCIENCE, 2003, 304 (1-3) : 471 - 476
  • [23] LINEAR-TIME ALGORITHMS AND NP-COMPLETE PROBLEMS
    GRANDJEAN, E
    SIAM JOURNAL ON COMPUTING, 1994, 23 (03) : 573 - 597
  • [24] Autoreducibility of NP-Complete Sets under Strong Hypotheses
    John M. Hitchcock
    Hadi Shafei
    computational complexity, 2018, 27 : 63 - 97
  • [25] 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
  • [26] Graph decomposition is NP-complete: A complete proof of Holyer's conjecture
    Dor, D
    Tarsi, M
    SIAM JOURNAL ON COMPUTING, 1997, 26 (04) : 1166 - 1187
  • [27] Recognizing Union-Find trees is NP-complete
    Gelle, Kitti
    Ivan, Szabolcs
    INFORMATION PROCESSING LETTERS, 2018, 131 : 7 - 14
  • [28] Finding a tree structure in a resolution proof is NP-complete
    Hoffmann, Jan
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2295 - 2300
  • [29] The minimal logically-defined NP-complete problem
    Barbanchon, R
    Grandjean, E
    STACS 2004, PROCEEDINGS, 2004, 2996 : 338 - 349
  • [30] k-LSAT is NP-Complete for k≥3
    Xu, Dao-Yun
    Deng, Tian-Yan
    Zhang, Qing-Shun
    Ruan Jian Xue Bao/Journal of Software, 2008, 19 (03): : 511 - 521
12345