| 大会名称 |
| 2022年 総合大会 |
| 大会コ－ド |
| 2022G |
| 開催年 |
|
2022
|
| 発行日 |
|
2022-03-01
|
| セッション番号 |
|
D-1
|
| セッション名 |
|
コンピュテーション
|
| 講演日 |
|
2022/3/17
|
| 講演場所(会議室等) |
|
Meeting 37
|
| 講演番号 |
|
D-1-12
|
| タイトル |
|
Finding a Shortest Solution for Single-Player Chinese Checkers is NP-complete
|
| 著者名 |
|
Yuya Nakamura, ○Yasuhiko Takenaga,
|
| キーワード |
|
game, NP-completeness, Chinese Checkers
|
| 抄録 |
|
Chinese Checkers is a strategy board game played by at most six players on a hexagram-shaped game board. Chinese Checkers with slightly different rules is called Diamond Game. In this paper, we consider a single-player version of Chinese Checkers played on arbitrary graphs. We prove that it is NP-complete to find the shortest solution of the game.
|
| 本文pdf |
|
PDF download
|
