JAIST Repository >
b. 情報科学研究科・情報科学系 >
b11. 会議発表論文・発表資料等 >
b11-1. 会議発表論文・発表資料 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/11619

タイトル: Computational complexity and an integer programming model of Shakashaka
著者: Demaine, Erik D.
Okamoto, Yoshio
Uehara, Ryuhei
Uno, Yushi
キーワード: integer programming
NP-completeness
pencil-and-paper puzzle
Shakashaka
発行日: 2013-08
出版者: CCCG
誌名: Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)
開始ページ: 31
終了ページ: 36
抄録: 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.
Rights: Copyrights of the article is maintained by the authors. Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara and Yushi Uno, Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), 2013, 31-36.
URI: http://hdl.handle.net/10119/11619
資料タイプ: author
出現コレクション:b11-1. 会議発表論文・発表資料 (Conference Papers)

このアイテムのファイル:

ファイル 記述 サイズ形式
19459.pdf129KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係