Computational Complexity and an Integer Programming Model of Shakashaka

Erik D. DEMAINE  Yoshio OKAMOTO  Ryuhei UEHARA  Yushi UNO  

Publication
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
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
integer programming,  NP-completeness,  pencil-and-paper puzzle,  Shakashaka,  

Full Text: PDF(1.5MB)
>>Buy this Article


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