Modelling and solving English Peg Solitaire

Christopher Jefferson; Angela Miguel; Ian Miguel; S. Armagan Tarim

doi:10.1016/j.cor.2005.01.018

Modelling and solving English Peg Solitaire

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	2935-2959
Number of pages	25
Journal	Computers and Operations Research
Volume	33
Issue number	10
DOIs	https://doi.org/10.1016/j.cor.2005.01.018
Publication status	Published - 1 Oct 2006

Keywords

Constraint programming
Integer programming
Modelling
Planning
Symmetry

Access to Document

10.1016/j.cor.2005.01.018

Cite this

@article{024a9af650f342fa80e71918bb9411fb,

title = "Modelling and solving English Peg Solitaire",

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, Planning, Symmetry",

author = "Christopher Jefferson and Angela Miguel and Ian Miguel and Tarim, \{S. Armagan\}",

year = "2006",

month = oct,

day = "1",

doi = "10.1016/j.cor.2005.01.018",

language = "English",

volume = "33",

pages = "2935--2959",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

number = "10",

}

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 - https://www.scopus.com/pages/publications/32044434438

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 -

Modelling and solving English Peg Solitaire

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this