Modelling and solving English Peg Solitaire
Modelling and solving English Peg Solitaire
复制标题
英式纸牌建模与求解
DOI：
10.1016/j.cor.2005.01.018
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Armagan Tarim
中科院分区：
文献类型：
--
作者：
Christopher Jefferson;Angela Miguel;Ian Miguel;Armagan Tarim
Peg Solitaire是一款众所周知的益智游戏，尽管它的规则很简单，但却很难。在板上设置钉，使得至少保留一个“孔”。通过跳棋/跳棋式的移动，棋子逐渐被移走，直到没有进一步的移动可能或达到一些目标配置。本文考虑的是英文版本，由一个有33个孔的十字形棋盘组成。通过约束或整数规划技术建模Peg纸牌提出了相当大的挑战，并详细检查。讨论了所得模型的优点，并进行了经验比较。谜题的顺序本质自然符合计划问题，因此我们也呈现了与几个领先的AI计划系统的实验比较。该游戏的其他变体，如“傻瓜纸牌”和“长跳纸牌”也在考虑之列。
Peg Solitaire is a well known puzzle, which can prove difficult despite its simple rules. Pegs are arranged on a board such that at least one ‘hole’ remains. By making draughts/checkers-like moves, pegs are gradually removed until no further moves are possible or some goal configuration is achieved. This paper considers the English variant, consisting of a board in a cross shape with 33 holes. Modelling Peg Solitaire via constraint or integer programming techniques presents a considerable challenge and is examined in detail. The merits of the resulting models are discussed and they are compared empirically. The sequential nature of the puzzle naturally conforms to a planning problem, hence we also present an experimental comparison with several leading AI planning systems. Other variants of the puzzle, such as ‘Fool's Solitaire’ and ‘Long-hop’ Solitaire are also considered.