Paper by Erik D. Demaine
- 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.
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.
- The paper is 6 pages.
- 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.
These pages are generated automagically from a
Last updated July 7, 2020 by