| 講演名 | 2016-09-06 Counting the number of solutions for peg solitaire 兼本 樹(神戸大), 斎藤 寿樹(神戸大), 清見 礼(横浜市大), 上原 隆平(北陸先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ペグソリティアは，最も古典的で有名なパズルのひとつであり，世界中で楽しまれている．一般化したペグソリティアは，NP完全問題であることが1990年代初頭に証明されている．そのため，理論計算機的な観点からはこれは手におえない問題であると見なされている．実際のパズルでは，盤面に33個の穴があり，この上に32個のペグを置いて遊ぶ．このパズルにはさまざまな解があることが知られており，パズルプレーヤーが手で見つけたものもあれば，1990年代に発見的なアルゴリズムで求めたものもある．本論文では，近年のコンピューターを使えば，この実際の盤面におけるすべての解を効率よく見つけられることを示す．正確には，ペグソリティアの解の総数を求めるアルゴリズムをいくつか提案する．これらを実装したプログラムは効率よく動作し，妥当な時間内に計算を終える． |
| 抄録(英) | Peg solitaire is one of the most popular classic puzzles around the world. The problem is NP-complete in general, which was shown in early 1990s. Therefore, it seems that it is intractable from the viewpoint of theoretical computer science. The real puzzle consists of board of 33 holes and 32 pegs, and a lot of solutions had found by puzzle players by hands, and heuristic algorithms developed in 1990s. We show that recent computer can find all possible solutions for this real puzzle in efficiency. Precisely, we propose some algorithms to count the number of solutions for the peg solitaire. They run efficiently, and we obtain the number of solutions in a reasonable computing time. |
| キーワード(和) | パズル / 数え上げアルゴリズム / アルゴリズム工学 |
| キーワード(英) | Puzzles / Counting algorithms / Algorithm engineering |
| 資料番号 | COMP2016-14 |
| 発行日 | 2016-08-30 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2016/9/6(から1日開催) |
| 開催地（和） | 富山県立大学 |
| 開催地（英） | Toyama Prefectural University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) |
| 委員長氏名（英） | Hiroo Itoh(Univ. of Electro-Comm.) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yuushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(神戸大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kobe Univ.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Counting the number of solutions for peg solitaire |
| サブタイトル（和） | |
| キーワード(1)（和/英） | パズル / Puzzles |
| キーワード(2)（和/英） | 数え上げアルゴリズム / Counting algorithms |
| キーワード(3)（和/英） | アルゴリズム工学 / Algorithm engineering |
| 第 1 著者 氏名（和/英） | 兼本 樹 / Itsuki Kanemoto |
| 第 1 著者 所属（和/英） | 神戸大学(略称：神戸大) Kobe University(略称：Kobe Univ.) |
| 第 2 著者 氏名（和/英） | 斎藤 寿樹 / Toshiki Saitoh |
| 第 2 著者 所属（和/英） | 神戸大学(略称：神戸大) Kobe University(略称：Kobe Univ.) |
| 第 3 著者 氏名（和/英） | 清見 礼 / Masashi Kiyomi |
| 第 3 著者 所属（和/英） | 横浜市立大学(略称：横浜市大) Yokohama City University(略称：Yokohama City Univ.) |
| 第 4 著者 氏名（和/英） | 上原 隆平 / Ryuhei Uehara |
| 第 4 著者 所属（和/英） | 北陸先端科学技術大学院大学(略称：北陸先端大) Japan Advanced Institute of Science and Technology(略称：JAIST) |
| 発表年月日 | 2016-09-06 |
| 資料番号 | COMP2016-14 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | COMP-211 |
| ページ範囲 | pp.1-5(COMP), |
| ページ数 | 5 |
| 発行日 | 2016-08-30 (COMP) |