Document Open Access Logo

Large Peg-Army Maneuvers

Authors Luciano Gualà, Stefano Leucci, Emanuele Natale, Roberto Tauraso

PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.18.pdf
  • Filesize: 0.65 MB
  • 15 pages

Document Identifiers

Author Details

Luciano Gualà
Stefano Leucci
Emanuele Natale
Roberto Tauraso

Cite As Get BibTex

Luciano Gualà, Stefano Leucci, Emanuele Natale, and Roberto Tauraso. Large Peg-Army Maneuvers. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FUN.2016.18

Abstract

Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algorithmic flavour which are related with this game, namely Solitaire-Reachability and Solitaire-Army. In the first one, we show that deciding whether there is a sequence of jumps which allows a given initial configuration of pegs to reach a target position is NP-complete. Regarding Solitaire-Army, the aim is to successfully deploy an army of pegs in a given region of the board in order to reach a target position. By solving an auxiliary problem with relaxed constraints, we are able to answer some open questions raised by Csakany and Juhasz (Mathematics Magazine, 2000).

Subject Classification

Keywords
  • Complexity of Games
  • Solitaire Army

Metrics

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

References

  1. M. Aigner. Moving into the Desert with Fibonacci. Math. Magazine, 70(1):11-21, 1997. Google Scholar
  2. G. Aloupis, E. D. Demaine, A. Guo, and G. Viglietta. Classic Nintendo games are (computationally) hard. Theoretical Computer Science, 586:135-160, 2015. Google Scholar
  3. J. D. Beasley. The Ins and Outs of Peg Solitaire. Oxford University Press, 1985. Google Scholar
  4. J. D. Beasley. Solitaire: Recent Developments. arXiv:0811.0851, 2008. Google Scholar
  5. J. D. Beasley. John and Sue Beasley’s Webpage on Peg Solitaire, 2015. URL: http://jsbeasley.co.uk/pegsol.htm.
  6. G. I. Bell. A Fresh Look at Peg Solitaire. Mathe.Magazine, 80(1):16-28, 2007. Google Scholar
  7. G. I. Bell, D. S. Hirschberg, and P. Guerrero-Garcia. The minimum size required of a solitaire army. arXiv/0612612, 2006. Google Scholar
  8. E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays, Volume 2. AK Peters, 2002. Google Scholar
  9. A. Bialostocki. An application of elementary group theory to central solitaire. The College Mathematics Journal, 29(3):208, 1998. Google Scholar
  10. F. Chung, R. Graham, J. Morrison, and A. Odlyzko. Pebbling a Chessboard. The American Mathematical Monthly, 102(2):113-123, 1995. Google Scholar
  11. B. Csakany and R. Juhasz. The Solitaire Army Reinspected. Math. Magazine, 73(5):354-362, 2000. Google Scholar
  12. E. W. Dijkstra. The checkers problem told to me by M.O. Rabin, 1992. URL: http://www.cs.utexas.edu/users/EWD/ewd11xx/EWD1134.PDF.
  13. E. W. Dijkstra. Only a matter of style?, 1995. URL: http://www.cs.utexas.edu/users/EWD/ewd12xx/EWD1200.PDF.
  14. M. Gardner. The Unexpected Hanging and Other Mathematical Diversions. University of Chicago Press, 1991. Google Scholar
  15. L. Guala, S. Leucci, and E. Natale. Bejeweled, Candy Crush and other match-three games are (NP-)hard. In CIG 2014, pages 1-8, 2014. Google Scholar
  16. R. A. Hearn and E. D. Demaine. Games, puzzles, and computation. AK Peters, 2009. Google Scholar
  17. R. Honsberger. A problem in checker jumping. Mathematical Gems II, pages 23-28, 1976. Google Scholar
  18. C. Jefferson, A. Miguel, I. Miguel, and S. A. Tarim. Modelling and solving English Peg Solitaire. Computers &Operations Research, 33(10):2935-2959, 2006. Google Scholar
  19. M. Kiyomi and T. Matsui. Integer Programming Based Algorithms for Peg Solitaire Problems. In Computers and Games, number 2063 in LNCS, pages 229-240. Springer, 2000. Google Scholar
  20. C. Moore and D. Eppstein. One-Dimensional Peg Solitaire, and Duotaire. arXiv/0008172, 2000. Google Scholar
  21. B. Ravikvmar. Peg-solitaire, string rewriting systems and finite automata. In Algorithms and Computation, volume 1350, pages 233-242. Springer, 1997. Google Scholar
  22. R. Uehara and S. Iwata. Generalized Hi-Q is NP-Complete. IEICE TRANSACTIONS, E73-E(2):270-273, 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact