Modelling and solving English Peg Solitaire |
| |
Authors: | Christopher Jefferson Angela Miguel Ian Miguel S. Armagan Tarim |
| |
Affiliation: | 1. Department of Computer Science, Artificial Intelligence Group, University of York, Heslington, York, YO10 5DD, UK;2. Department of Management, Hacettepe University, Ankara, Turkey |
| |
Abstract: | 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. |
| |
Keywords: | Constraint programming Integer programming Modelling Symmetry Planning |
本文献已被 ScienceDirect 等数据库收录! |
|