| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-09-16 |
| タイトル |
|
|
タイトル |
Experimental Enumeration of Solutions for Peg Solitaire (Short Talk) |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Experimental Enumeration of Solutions for Peg Solitaire (Short Talk) |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
National Institute of Technology, Ichinoseki College |
| 著者所属 |
|
|
|
Kobe University |
| 著者所属 |
|
|
|
Kobe University |
| 著者所属 |
|
|
|
Yokohama City University |
| 著者所属 |
|
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Technology, Ichinoseki College |
| 著者所属(英) |
|
|
|
en |
|
|
Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama City University |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Science and Technology |
| 著者名 |
Taishi, Oikawa
Itsuki, Kanemoto
Toshiki, Saitoh
Masashi, Kiyomi
Ryuhei, Uehara
|
| 著者名(英) |
Taishi, Oikawa
Itsuki, Kanemoto
Toshiki, Saitoh
Masashi, Kiyomi
Ryuhei, Uehara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. Martin Gardner said that “No one knows how many different ways there are to solve the puzzle leaving the last counter in the center” in his book. One of the authors once developped a heuristic algorithms in 1990, and found some of them. In his master thesis, he said “it is impossible to find all solutions in this search tree” in 1991. We show that recent computer can find all possible solutions for this real puzzle in efficiency. We develop 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. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. Martin Gardner said that “No one knows how many different ways there are to solve the puzzle leaving the last counter in the center” in his book. One of the authors once developped a heuristic algorithms in 1990, and found some of them. In his master thesis, he said “it is impossible to find all solutions in this search tree” in 1991. We show that recent computer can find all possible solutions for this real puzzle in efficiency. We develop 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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-159,
号 3,
p. 1-1,
発行日 2016-09-16
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16159003.pdf (345.3 kB)
