Solitaire Army Problems

This page contains the solutions to the Solitaire Army Problem as described in the paper Large Peg-Army Maneuvers published in the Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016).

The game of Peg Solitaire

Not so very long ago there became widespread an excellent kind of game, called Solitaire, where I play on my own, but as if with a friend as witness and referee to see that I play correctly. A board is filled with stones set in holes, which are to be removed in turn, but none (except the first, which may be chosen for removal at will) can be removed unless you are able to jump another stone across it into an adjacent empty place, when it is captured as in Draughts. He who removes all the stones right to the end according to this rule, wins; but he who is compelled to leave more than one stone still on the board, yields the palm. This game can more elegantly be played backwards, after one stone has been put at will on an empty board, by placing the rest with it, but the same rule being observed for the addition of stones as was stated just above for their removal. Thus we can either fill the board, or, what would be more clever, shape a predetermined figure from the stones; perhaps a triangle, a quadrilateral, an octagon, or some other, if this be possible; but such a task is by no means always possible: and this itself would be a valuable art, to foresee what can be achieved; and to have some way, particularly geometrical, of determining this.

— Gottfried Wilhelm Leibniz
Original Latin text in Miscellanea Berolinensia 1, 1710, p. 24.
The given translation is from J. D. Beasley. The Ins and Outs of Peg Solitaire. Oxford University Press, 1985.

The Solitaire Army Problem

In the Solitaire Army Problem, given a region of an infinite board called desert and a target position inside it, one is asked to find an initial configuration of pegs outside that region, and a finite sequence of moves that allows some peg to be placed in the given target position.

Play the game

Here you can play the game on different deserts. In the reverse problem the goal is to remove all the pegs from the desert. In the forward problem you start with a configurations of pegs and your goal is to bring a peg to the center of the desert.
Square 7x7 (easy)Forward Reverse
Square 9x9Forward Reverse
Square 11x11Forward Reverse
Rhombus 11x11 (easy)Forward Reverse
Rhombus 13x13Forward Reverse
Rhombus 15x15Forward Reverse

Our solutions

DesertGoalNumber of movesSolution
Square 7x7Center of the desert15Forward Reverse Moves
Square 9x9Center of the desert39Forward Reverse Moves
Square 11x11Center of the desert246Included in the paper
Square 11x11 (alternate)Center of the desert212Forward Reverse Moves
Square 12x12One of the four centers of the desert301Forward Reverse Moves
Square 11x11 at the border of the board, when the board is a half-planeCenter of the desert246Forward Reverse Moves
Square 11x11, when the board is the union of three half-planes tangent to the desertCenter of the desert241Forward Reverse Moves
Rhombus 13x13 (i.e. with axes of length 13)Center of the desert58Forward Reverse Moves
Rhombus 15x15 (i.e. with axes of length 15)Center of the desert176Forward Reverse Moves
Rhombus 15x15 at the border of the board, when the board is a diagonal half-planeCenter of the desert202Forward Reverse Moves
Rhombus 15x15, when the board is the union of three half-planes tangent to the desertCenter of the desert183Forward Reverse Moves

About the authors

We are an Italian group of four people: Luciano Gualà, Stefano Leucci, Emanuele Natale, and Roberto Tauraso.