**Reference**:- Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno, “Computational complexity and an integer programming model of Shakashaka”, in
*Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)*, Waterloo, Ontario, Canada, August 8–10, 2013, to appear. **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 if #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.
**Length**:- The paper is 6 pages.
**Availability**:- The paper is available in PostScript (1167k), gzipped PostScript (406k), and PDF (344k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Shakashaka_IEICE (Computational complexity and an integer programming model of Shakashaka)

See also other papers by Erik Demaine.

Last updated July 21, 2021 by Erik Demaine.