| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-09-06 10:30 Counting the number of solutions for peg solitaire ○Itsuki Kanemoto・Toshiki Saitoh（Kobe Univ.）・Masashi Kiyomi（Yokohama City Univ.）・Ryuhei Uehara（JAIST）  COMP2016-14 |
|
| 抄録 | （和） | ペグソリティアは，最も古典的で有名なパズルのひとつであり，世界中で楽しまれている．一般化したペグソリティアは，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 / / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 211, COMP2016-14, pp. 1-5, 2016年9月. | |
| 資料番号 | COMP2016-14 | |
| 発行日 | 2016-08-30 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-14 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2016-09-06 - 2016-09-06 |
| 開催地（和） | 富山県立大学 |
| 開催地（英） | Toyama Prefectural University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Counting the number of solutions for peg solitaire |
| サブタイトル（英） | |
| キーワード(1)（和/英） | パズル / Puzzles |
| キーワード(2)（和/英） | 数え上げアルゴリズム / Counting algorithms |
| キーワード(3)（和/英） | アルゴリズム工学 / Algorithm engineering |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-09-06 10:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-14 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.211 |
| ページ範囲 | pp.1-5 |
| ページ数 | 5 |
| 発行日 | 2016-08-30 (COMP) |
[研究会発表申込システムのトップページに戻る]