BLOCKSUM is NP-Complete

Kazuya HARAGUCHI  Hirotaka ONO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.481-488
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.481
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
NP-completeness,  combinatorial puzzle,  Latin square,  BLOCKSUM,  

Full Text: PDF(1003.6KB)>>
Buy this Article




Summary: 
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.