Modelling and solving English Peg Solitaire

Christopher Jefferson, Angela Miguel, Ian Miguel*, S. Armagan Tarim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)2935-2959
Number of pages25
JournalComputers and Operations Research
Volume33
Issue number10
DOIs
Publication statusPublished - 1 Oct 2006

Keywords

  • Constraint programming
  • Integer programming
  • Modelling
  • Planning
  • Symmetry

Fingerprint

Dive into the research topics of 'Modelling and solving English Peg Solitaire'. Together they form a unique fingerprint.

Cite this