講演抄録/キーワード |
講演名 |
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 |