Paper Info
Title
Computational Complexity And An Integer Programming Model Of Shakashaka
Abstract
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.
Year
DOI
Venue
2013
10.1587/transfun.E97.A.1213
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
DocType
Volume
integer programming, NP-completeness, pencil-and-paper puzzle, Shakashaka
Conference
E97A
Issue
ISSN
Citations 
6
1745-1337
2
PageRank 
References 
Authors
0.39
5
4
Name
Order
Citations
PageRank
Erik D. Demaine14624388.59
Yoshio Okamoto217028.50
Ryuhei Uehara352875.38
yushi uno422228.80