For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
BLOCKSUM is NP-Complete
Kazuya HARAGUCHI Hirotaka ONO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Online ISSN: 1745-1361
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 —)
NP-completeness, combinatorial puzzle, Latin square, BLOCKSUM,
Full Text: PDF(1003.6KB)>>
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.