Modelling and solving English Peg Solitaire

Jefferson C., Miguel A., Miguel I., Tarim Ş. A.

COMPUTERS & OPERATIONS RESEARCH, cilt.33, sa.10, ss.2935-2959, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 33 Sayı: 10
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.cor.2005.01.018
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2935-2959
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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. (c) 2005 Elsevier Ltd. All rights reserved.