2026-08-17T14:19:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8799 2024-03-06T10:42:41Z ddc:004 open_access

On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games Bilò, Davide Gualà, Luciano Leucci, Stefano Proietti, Guido Rossi, Mirko peg duotaire pspace-completeness peg solitaire two-player games 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Luciano Gualà and Stefano Leucci and Guido Proietti and Mirko Rossi 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.8 urn:nbn:de:0030-drops-87994 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode