Peg Solitaire

Given an initial and a final configuration of pegs on a board, find a sequence of peg-solitaire moves that transforms the initial configuration into the final one.

Description

In Peg Solitaire (also known as Hi-Q), we have a grid graph (the board) on each of whose nodes (the holes) there may be at most one peg. The initial configuration of pegs evolves by performing one of the following moves (the jumps): for each triple of horizontally or vertically adjacent nodes, if the first and the second nodes are occupied by pegs and there is no peg on the third one, then we can remove the two pegs and place a new one on the third node.

A puzzle of peg solitaire is defined by an initial and a final configuration, and consists of finding a sequence of moves that transforms the initial configuration into the final one.

Solitaire Army is based on the game mechanics of Peg Solitaire.

Peg Duotaire is a two-player variant of Peg Solitaire in which two players alternatively make a peg move and the winner is the last player to move.

Peg Solitaire Reachability is a puzzle in which, given an initial configuration of pegs on a finite board, one is asked to determine whether there exists a sequence of Peg-Solitaire moves that allows any peg to be placed in a given target position.

Computational Complexity

[1] proves the NP-completeness of those peg solitaire puzzles in which the final configuration is required to have only one peg (hence, the goal is cleaning the entire board). However, for rectangular boards of fixed (constant) height, deciding whether a given configuration can be transformed into a single peg is polynomial-time solvable, since solvable instances form a regular language [2].

[3] proves the NP-completeness of the Peg Solitaire Reachability problem.

References

[1] R. Uehara and S. Iwata. “Generalized Hi-Q is NP-Complete”, IEICE TRANSACTIONS, 1990.

[2] B. Ravikumar, “Peg-solitaire, string rewriting systems and finite automata”, Theoretical Computer Science, 2004.

[3] L. Gualà, S. Leucci, E. Natale, and R. Tauraso. “Large Peg-Army Maneuvers”, in FUN 2016.