| Presentation | 2016-09-06 Counting the number of solutions for peg solitaire Itsuki Kanemoto, Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Puzzles / Counting algorithms / Algorithm engineering |
| Paper # | COMP2016-14 |
| Date of Issue | 2016-08-30 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2016/9/6(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Toyama Prefectural University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Counting the number of solutions for peg solitaire |
| Sub Title (in English) | |
| Keyword(1) | Puzzles |
| Keyword(2) | Counting algorithms |
| Keyword(3) | Algorithm engineering |
| 1st Author's Name | Itsuki Kanemoto |
| 1st Author's Affiliation | Kobe University(Kobe Univ.) |
| 2nd Author's Name | Toshiki Saitoh |
| 2nd Author's Affiliation | Kobe University(Kobe Univ.) |
| 3rd Author's Name | Masashi Kiyomi |
| 3rd Author's Affiliation | Yokohama City University(Yokohama City Univ.) |
| 4th Author's Name | Ryuhei Uehara |
| 4th Author's Affiliation | Japan Advanced Institute of Science and Technology(JAIST) |
| Date | 2016-09-06 |
| Paper # | COMP2016-14 |
| Volume (vol) | vol.116 |
| Number (no) | COMP-211 |
| Page | pp.pp.1-5(COMP), |
| #Pages | 5 |
| Date of Issue | 2016-08-30 (COMP) |