Computational Complexity and an Integer Programming Model of Shakashaka

• DEMAINE Erik D.

  MIT Computer Science and Artificial Intelligence Laboratory

• OKAMOTO Yoshio

  Graduate School of Informatics and Engineering, The University of Electro-Communications

• UEHARA Ryuhei

  School of Information Science, JAIST

• UNO Yushi

  Graduate School of Science, Osaka Prefecture University

抄録

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.

収録刊行物

• 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

  一般社団法人 電子情報通信学会

キーワード

• integer programming
• NP-completeness
• pencil-and-paper puzzle
• Shakashaka

詳細情報

• CRID: 1390001206310314240
• NII論文ID: 130004770851
• DOI: 10.1587/transfun.e97.a.1213
• ISSN: 17451337
• ISSN: 09168508
• Web Site: http://hdl.handle.net/10119/12147
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E97.A/6/E97.A_1213/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可