文章基本信息

标题：Large Peg-Army Maneuvers
本地全文：下载
作者：Luciano Gual{\`a ; Stefano Leucci ; Emanuele Natale 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：49
页码：18:1-18:15
DOI：10.4230/LIPIcs.FUN.2016.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Complexity of Games; Solitaire Army