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.
Computational Complexity and an Integer Programming Model of Shakashaka
Erik D. DEMAINE Yoshio OKAMOTO Ryuhei UEHARA Yushi UNO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
integer programming, NP-completeness, pencil-and-paper puzzle, Shakashaka,
Full Text: PDF>>
Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.