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   Vol.E97-A   No.6   pp.1213-1219
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1213
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>>
Buy this Article

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.