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 [J].

Ito, Kazushi ;

Takenaga, Yasuhiko .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2023, E106D (06) :1111-1116

[22] On universally easy classes for NP-complete problems [J].

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 [J].

GRANDJEAN, E .

SIAM JOURNAL ON COMPUTING, 1994, 23 (03) :573-597

[24] Autoreducibility of NP-Complete Sets under Strong Hypotheses [J].

John M. Hitchcock ;

Hadi Shafei .

computational complexity, 2018, 27 :63-97

[25] Packing cubes into a cube is NP-complete in the strong sense [J].

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 [J].

Dor, D ;

Tarsi, M .

SIAM JOURNAL ON COMPUTING, 1997, 26 (04) :1166-1187

[27] Finding a tree structure in a resolution proof is NP-complete [J].

Hoffmann, Jan .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) :2295-2300

[28] Recognizing Union-Find trees is NP-complete [J].

Gelle, Kitti ;

Ivan, Szabolcs .

INFORMATION PROCESSING LETTERS, 2018, 131 :7-14

[29] The minimal logically-defined NP-complete problem [J].

Barbanchon, R ;

Grandjean, E .

STACS 2004, PROCEEDINGS, 2004, 2996 :338-349

[30] k-LSAT is NP-Complete for k≥3 [J].

Xu, Dao-Yun ;

Deng, Tian-Yan ;

Zhang, Qing-Shun .

Ruan Jian Xue Bao/Journal of Software, 2008, 19 (03) :511-521

← 1 2 3 4 5 →