Large Peg-Army Maneuvers

Luciano Gualà, Stefano Leucci, Emanuele Natale, Roberto Tauraso

Abstract

This paper explores the computational complexity and mathematical depth of peg solitaire, a centuries-old game with deceptively simple rules. We prove that the problem of determining if a peg can reach a specific target (Solitaire-Reachability) is NP-complete. This is achieved by constructing a library of boolean logic gadgets from peg configurations, allowing the game to simulate planar circuits. Additionally, we address the "Solitaire-Army" problem, solving previously open puzzles such as the $11 \times 11$ square desert. Our approach utilizes a mathematical relaxation involving "negative pegs" and Integer Linear Programming (ILP), coupled with a reconstruction theorem that converts relaxed solutions back into valid game sequences.

Introduction

Peg solitaire has long fascinated mathematicians, including Leibniz and Conway. The game involves jumping one peg over another into an empty hole to remove the jumped peg. While traditionally played on small boards, its algorithmic properties on larger grids reveal a deep logical structure. This research tackles two primary challenges: the formal complexity of reachability and the solution of "army" puzzles where pegs must conquer an empty "desert" region.

Complexity of Solitaire-Reachability

The authors establish that Solitaire-Reachability is NP-complete via a reduction from Planar Circuit Satisfiability (PCSat). To bridge the gap between a board game and boolean logic, the authors developed specialized "gadgets"—arrangements of pegs that function as logic gates and signal carriers.

Encoding boolean logic into peg solitaire configurations using specialized gadgets such as Fan-Out and AND gates.

Gadget Design and Dual-Rail Logic

A significant challenge in peg solitaire is the absence of a natural "NOT" gate. To resolve this, the authors employed dual-rail logic, representing a single boolean value with two parallel "wires" (one for TRUE, one for FALSE). Furthermore, to handle the constraints of a 2D grid, they designed "control-crossover" gadgets to allow signals to cross without interference.

Physical peg arrangements required to implement single wires, shifts, and half-crossovers on the solitaire grid.

Solving the Solitaire-Army Problem

The Solitaire-Army problem involves moving a peg into an empty region (the "desert") starting from an "army" of pegs outside it. The primary difficulty lies in the temporal dependency of moves. To bypass this, the authors introduced R-Solitaire-Army, a relaxed version where nodes can hold any integer number of pegs, including negative integers.

This relaxation transforms a difficult temporal problem into a static spatial flow problem, which the authors modeled as an Integer Linear Program (ILP). Crucially, they proved a reconstruction theorem: any solution found in the relaxed world can be converted back into a valid, sequence-dependent solution in the real game in polynomial time.

Key Results

Using the ILP framework and the Gurobi optimizer, the authors successfully solved several long-standing open questions:

  • $11 \times 11$ Square Desert: Solvable in 212 moves.
  • $15 \times 15$ Rhombus Desert: Solvable in 176 moves.
  • $12 \times 12$ Square Desert: Solvable in 301 moves.

These results provide the first explicit move sequences for these difficult configurations, demonstrating the power of the ILP relaxation method.

Conclusion

This work elegantly bridges recreational mathematics and formal complexity theory. By proving the NP-completeness of reachability and providing a robust framework for solving army puzzles, the authors demonstrate that even a 17th-century board game contains sophisticated computational secrets. Future work may extend these methods to optimize for the minimum number of pegs required or explore properties on truly infinite boards.

Summary updated

BibTeX
@inproceedings{guala2016large,
  author = {Luciano Gualà and Stefano Leucci and Emanuele Natale and Roberto Tauraso},
  title = {{Large Peg-Army Maneuvers}},
  booktitle = {FUN},
  year = {2016},
  url = {https://openreview.net/forum?id=yRwM2pFjJ4Y},
}
Figure