IEICE TRANSACTIONS on Fundamentals
Computational Complexity and an Integer Programming Model of Shakashaka
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1213-1219
- Publication Date
- 2014/06/01
- Publicized
- 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)
- Category
Authors
Erik D. DEMAINE
MIT Computer Science and Artificial Intelligence Laboratory
Yoshio OKAMOTO
The University of Electro-Communications
Ryuhei UEHARA
JAIST
Yushi UNO
Osaka Prefecture University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Erik D. DEMAINE, Yoshio OKAMOTO, Ryuhei UEHARA, Yushi UNO, "Computational Complexity and an Integer Programming Model of Shakashaka" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1213-1219, June 2014, doi: 10.1587/transfun.E97.A.1213.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1213/_p
Copy
@ARTICLE{e97-a_6_1213,
author={Erik D. DEMAINE, Yoshio OKAMOTO, Ryuhei UEHARA, Yushi UNO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity and an Integer Programming Model of Shakashaka},
year={2014},
volume={E97-A},
number={6},
pages={1213-1219},
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.},
keywords={},
doi={10.1587/transfun.E97.A.1213},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Computational Complexity and an Integer Programming Model of Shakashaka
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1213
EP - 1219
AU - Erik D. DEMAINE
AU - Yoshio OKAMOTO
AU - Ryuhei UEHARA
AU - Yushi UNO
PY - 2014
DO - 10.1587/transfun.E97.A.1213
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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.
ER -
English
