Open access
Date
2018Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Peg Duotaire is a two-player version of the classical puzzle called Peg Solitaire. Players take turns making peg-jumping moves, and the first player which is left without available moves loses the game. Peg Duotaire has been studied from a combinatorial point of view and two versions of the game have been considered, namely the single- and the multi-hop variant. On the other hand, understanding the computational complexity of the game is explicitly mentioned as an open problem in the literature. We close this problem and prove that both versions of the game are PSPACE-complete. We also prove the PSPACE-completeness of other peg-jumping games where two players control pegs of different colors. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000309435Publication status
publishedExternal links
Book title
Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
peg duotaire; pspace-completeness; peg solitaire; two-player gamesOrganisational unit
03340 - Widmayer, Peter / Widmayer, Peter
More
Show all metadata
ETH Bibliography
yes
Altmetrics