Document Open Access Logo

On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games

Authors Davide Bilò , Luciano Gualà , Stefano Leucci , Guido Proietti , Mirko Rossi

PDF

File

Thumbnail PDF
PDF
LIPIcs.FUN.2018.8.pdf
  • Filesize: 1.25 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • peg duotaire
  • pspace-completeness
  • peg solitaire
  • two-player games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.8

Author Details

Davide Bilò
  • Dipartimento di Scienze Umanistiche e Sociali, University of Sassari, Italy.
Luciano Gualà
  • Dipartimento di Ingegneria dell'Impresa, University of Rome "Tor Vergata", Italy.
Stefano Leucci
  • Institute of Theoretical Computer Science, ETH Zürich, Switzerland.
Guido Proietti
  • Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica, University of L'Aquila, Italy, and Istituto di Analisi dei Sistemi ed Informatica, CNR, Roma, Italy.
Mirko Rossi
  • Dipartimento di Ingegneria dell'Impresa, University of Rome "Tor Vergata", Italy.

References

  1. Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Trainyard is np-hard. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 2:1-2:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.2.
  2. John D. Beasley. The Ins and Outs of Peg Solitaire. Oxford University Press, Oxford Oxfordshire ; New York, 1985. Google Scholar
  3. John D. Beasley. Solitaire: Recent Developments. arXiv:0811.0851 [cs, math], nov 2008. arXiv: 0811.0851. URL: http://arxiv.org/abs/0811.0851.
  4. John D. Beasley. John and Sue Beasley’s Webpage on Peg Solitaire, oct 2015. URL: https://web.archive.org/web/20151010215541/http://jsbeasley.co.uk/pegsol.htm.
  5. George I. Bell. A Fresh Look at Peg Solitaire. Mathematics Magazine, 80(1):16-28, feb 2007. URL: http://www.jstor.org/stable/27642987.
  6. George I. Bell, Daniel S. Hirschberg, and Pablo Guerrero-Garcia. The minimum size required of a solitaire army. arXiv:math/0612612, 2006. arXiv: math/0612612. URL: http://arxiv.org/abs/math/0612612.
  7. Arie Bialostocki. An application of elementary group theory to central solitaire - ProQuest. URL: http://search.proquest.com/openview/5b321e9dd162151b018ab7d63304daf2/1?pq-origsite=gscholar.
  8. Bela Csakany and Rozalia Juhasz. The Solitaire Army Reinspected. Mathematics Magazine, 73(5):354-362, dec 2000. Google Scholar
  9. Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, and Scott Aaronson. The Fewest Clues Problem. In 8th International Conference on Fun with Algorithms (FUN 2016), volume 49, pages 12:1-12:12, 2016. Google Scholar
  10. Edsger W. Dijkstra. The checkers problem told to me by M.O. Rabin, 1992. URL: http://www.cs.utexas.edu/users/EWD/ewd11xx/EWD1134.PDF.
  11. Martin Gardner. The Unexpected Hanging and Other Mathematical Diversions. University of Chicago Press, Chicago, nov 1991. Google Scholar
  12. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1990. Google Scholar
  13. J. P. Grossman. Periodicity in one-dimensional peg duotaire. Theor. Comput. Sci., 313(3):417-425, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2002.11.003.
  14. Luciano Gualà, Stefano Leucci, and Emanuele Natale. Bejeweled, candy crush and other match-three games are (np-)hard. In 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014, pages 1-8. IEEE, 2014. URL: http://dx.doi.org/10.1109/CIG.2014.6932866.
  15. Luciano Gualà, Stefano Leucci, Emanuele Natale, and Roberto Tauraso. Large peg-army maneuvers. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 18:1-18:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.18.
  16. Robert A. Hearn. Amazons, Konane, and Cross Purposes are PSPACE-complete, page 287–306. Mathematical Sciences Research Institute Publications. Cambridge University Press, 2009. URL: http://dx.doi.org/10.1017/CBO9780511807251.015.
  17. Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. AK Peters Wellesley, 2009. Google Scholar
  18. Ross Honsberger. A problem in checker jumping. Mathematical Gems II, pages 23-28, 1976. Google Scholar
  19. David Lichtenstein and Michael Sipser. GO is polynomial-space hard. J. ACM, 27(2):393-401, 1980. URL: http://dx.doi.org/10.1145/322186.322201.
  20. Neeldhara Misra. Two dots is np-complete. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 24:1-24:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.24.
  21. Cristopher Moore and David Eppstein. One-Dimensional Peg Solitaire, and Duotaire. arXiv:math/0008172, 2000. arXiv: math/0008172. URL: http://arxiv.org/abs/math/0008172.
  22. Bala Ravikumar. Peg-solitaire, string rewriting systems and finite automata. Theor. Comput. Sci., 321(2-3):383-394, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.05.005.
  23. Ryuhei Uehara and Shigeki Iwata. Generalized Hi-Q is NP-Complete. IEICE TRANSACTIONS (1976-1990), E73-E(2):270-273, feb 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact