prob037: Peg Solitaire
Modelling
Peg Solitaire is essentially a planning problem: the goal is to find a sequence
of actions that transform the initial state into the goal state. We are helped
by the fact that we know exactly how many moves are necessary: (the number
of pegs in the initial configuration - the number of pegs in the goal
configuration). A CP model found to be successful in [1] employs a 1-dimensional
array of variables, moves[t], which records the move made
at time-step t. The domain
of each element of this array is the set of possible moves, i.e. all
ways of removing a peg from the board. The number of possibilities will vary
according to the board shape, but the English board has 76 such possible moves.
A second array, bState[i, j, t] of 01 variables (where
i, j specify a board position and t is the time-step), is used to keep track of the
state of the board before and after each move. This array is used also to specify
the three pre-conditions (two pegs and a hole) and three post-conditions
(two holes and a peg) of each possible move.
Symmetry
Peg Solitaire contains a lot of symmetry. Depending on the shape of the board,
rotation and reflection symmetries will usually apply. There are also symmetries
of independent moves: that is, entries in moves[] that can be exchanged
without affecting the solution. Symmetries of pairs of independent moves can
be broken by imposing an ordering on moves[] as follows. Symmetries of
larger groups of independent moves are more expensive to break.
independent(moves[i],
moves[i+1]) ->
moves[i] <=
moves[i+1]
There are also symmetric paths to the same board state. On some occasions this
is due to independent moves, but on others disjoint sets of moves can lead to
the same position. These symmetries can be broken by identifying the symmetric
paths and adding constraints to allow only one representative from each
equivalence class, but the identification process itself is expensive.
Other Models
As described in [1] a PDDL model suitable for use with AI planning systems can
easily be created, as can an integer programming model.
Fool's Solitaire
An optimisation variant of peg Solitaire is to attempt to reach a position
where no further moves are possible in the shortest sequence of moves.
This can be modelled by adding a special `DeadEnd' move to the domain of
each variable in moves[]. This move is only applicable when no other
move is possible. The problem is then to maximise the occurrences of
`DeadEnd' in moves[].
-
C. Jefferson, A. Miguel, I. Miguel, A. Tarim,
"Modelling
and Solving English Peg Solitaire,"
Proceedings of the Fifth International Workshop on Integration
of AI and OR Techniques in Constraint Programming for Combinatorial
Optimization Problems (CPAIOR'03), pp. 261--275, 2003.
Back to CSPLib home page.