DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2016.18

Large Peg-Army Maneuvers

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

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

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).

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{guala_et_al:LIPIcs.FUN.2016.18,
  author =	{Gual\`{a}, Luciano and Leucci, Stefano and Natale, Emanuele and Tauraso, Roberto},
  title =	{{Large Peg-Army Maneuvers}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.18},
  URN =		{urn:nbn:de:0030-drops-58709},
  doi =		{10.4230/LIPIcs.FUN.2016.18},
  annote =	{Keywords: Complexity of Games, Solitaire Army}
}

Search Results

Documents authored by Tauraso, Roberto

Large Peg-Army Maneuvers

Abstract

Cite as

Thanks for your feedback!

Could not send message