Computational Complexity and an Integer Programming Model of Shakashaka

Access this Article

Author(s)

    • OKAMOTO Yoshio
    • Graduate School of Informatics and Engineering, The University of Electro-Communications
    • UNO Yushi
    • Graduate School of Science, Osaka Prefecture University

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.

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.

Journal

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97.A(6), 1213-1219, 2014

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    130004770851
  • Text Lang
    ENG
  • Article Type
    Journal Article
  • ISSN
    0916-8508
  • Data Source
    IR  J-STAGE 
Page Top