| 講演名 | 2013-04-24 ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル ドメイン エリック・D, 岡本 吉央, 上原 隆平, 宇野 裕之, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | パズル「シャカシャカ」は,有名な数独をはじめとする多くのペンシルパズルと同様,日本の出版社ニコリが普及させたパズルである.これまで「シャカシャカ」の計算複雑さは未解決であった.本稿ではまず「シャカシャカ」がNP完全であることを示す.次に「シャカシャカ」を整数計画問題として記述する.これを実装し,市販されている本の問題をIPソルバで解いた実験結果を示す.その結果,どの問題も1秒以内に解けた. |
| 抄録(英) | Shakashaka, one of the so-called "pencil-and-paper" puzzles like Sudoku, was proposed by Guten and has been popularized by the Japanese publisher Nikoli. The computational complexity of Shakashaka was not studied so far. We first prove that Shakashaka is NP-complete. Next we formulate Shakashaka as an integer programming problem. We apply the formulation to some instances appeared in a puzzle book, solve them by using an IP solver, and show the experimental results; each problem can be solved in a second. |
| キーワード(和) | 整数計画法 / NP完全性 / ペンシルパズル / シャカシャカ |
| キーワード(英) | integer programming / NP-completeness / pencil-and-paper puzzle / Shakashaka |
| 資料番号 | COMP2013-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2013/4/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル |
| サブタイトル（和） | |
| タイトル（英） | Computational complexity and an integer programming model of Shakashaka |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 整数計画法 / integer programming |
| キーワード(2)（和/英） | NP完全性 / NP-completeness |
| キーワード(3)（和/英） | ペンシルパズル / pencil-and-paper puzzle |
| キーワード(4)（和/英） | シャカシャカ / Shakashaka |
| 第 1 著者 氏名（和/英） | ドメイン エリック・D / Erik D. DEMAINE |
| 第 1 著者 所属（和/英） | マサチューセッツ工科大学 Massachusetts Institute of Technology(MIT) |
| 第 2 著者 氏名（和/英） | 岡本 吉央 / Yoshio OKAMOTO |
| 第 2 著者 所属（和/英） | 電気通信大学 The University of Electro-Communications(UEC) |
| 第 3 著者 氏名（和/英） | 上原 隆平 / Ryuhei UEHARA |
| 第 3 著者 所属（和/英） | 北陸先端科学技術大学院大学 Japan Advanced Institute of Science and Technology(JAIST) |
| 第 4 著者 氏名（和/英） | 宇野 裕之 / Yushi UNO |
| 第 4 著者 所属（和/英） | 大阪府立大学 Osaka Prefecture University(OPU) |
| 発表年月日 | 2013-04-24 |
| 資料番号 | COMP2013-8 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 14 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |