TY - JOUR
T1 - Modelling and solving English Peg Solitaire
AU - Jefferson, Christopher
AU - Miguel, Angela
AU - Miguel, Ian
AU - Tarim, S. Armagan
PY - 2006/10/1
Y1 - 2006/10/1
N2 - 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.
AB - 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.
KW - Constraint programming
KW - Integer programming
KW - Modelling
KW - Planning
KW - Symmetry
UR - http://www.scopus.com/inward/record.url?scp=32044434438&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2005.01.018
DO - 10.1016/j.cor.2005.01.018
M3 - Article
AN - SCOPUS:32044434438
SN - 0305-0548
VL - 33
SP - 2935
EP - 2959
JO - Computers and Operations Research
JF - Computers and Operations Research
IS - 10
ER -