Computational complexity and an integer programming model of Shakashaka

Access this Article

Abstract

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.

Journal

  • 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

    CCCG

Codes

  • NII Article ID (NAID)
    120006675375
  • Text Lang
    ENG
  • Article Type
    conference paper
  • Data Source
    IR 
Page Top