prob037: Peg Solitaire

proposed by

Chris Jefferson, Angela Miguel, Ian Miguel, and Armagan Tarim

caj@cs.york.ac.uk, angiem@cs.york.ac.uk, ianm@cs.york.ac.uk, at@cs.york.ac.uk

Specification

Peg Solitaire (also known as Hi-Q) is played on a board with a number of holes. In the English version of the game, the board is in the shape of a cross with 33 holes: OOO OOO OOOOOOO OOOOOOO OOOOOOO OOO OOO Pegs (`X's here) are arranged on the board so that at least one hole remains. A number of different problems arise from Solitaire, e.g. finding a path from the initial to a goal state, or finding the shortest number of moves to a state where no more moves are possible. Moves are draughts/checkers-like and are horizontal or vertical: XX0 -> OOX The following is the classic `central' version of the game: Start: Goal: XXX OOO XXX OOO XXXXXXX OOOOOOO XXXOXXX -> OOOXOOO XXXXXXX OOOOOOO XXX OOO XXX OOO The French version of the game has four extra holes: OOO OOOOO OOOOOOO OOOOOOO OOOOOOO OOOOO OOO Other board types, such as the Solitaire Triangle, also exist.

Back