Computational complexity and an integer programming model of Shakashaka
Access this Article
Shakashaka, one of the so-called "pencil-and-paper"puzzles like Sudoku, was proposed by Guten and hasbeen popularized by the Japanese publisher Nikoli. The computational complexity of Shakashaka was not studied so far. We first prove that Shakashaka is NPcomplete. Next we formulate Shakashaka as an integer programming problem. We apply the formulation to some concrete instances that appeared in a puzzle book, and solve them by using an IP solver, and show the experimental results; each problem can be solved in a second.
- Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)
Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), 31-36, 2013-08