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.
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.| Desert | Play |
|---|---|
| Square 7x7 (easy) | Forward Reverse |
| Square 9x9 | Forward Reverse |
| Square 11x11 | Forward Reverse |
| Rhombus 11x11 (easy) | Forward Reverse |
| Rhombus 13x13 | Forward Reverse |
| Rhombus 15x15 | Forward Reverse |
Our solutions
| Desert | Goal | Number of moves | Solution |
|---|---|---|---|
| Square 7x7 | Center of the desert | 15 | Forward Reverse Moves |
| Square 9x9 | Center of the desert | 39 | Forward Reverse Moves |
| Square 11x11 | Center of the desert | 246 | Included in the paper |
| Square 11x11 (alternate) | Center of the desert | 212 | Forward Reverse Moves |
| Square 12x12 | One of the four centers of the desert | 301 | Forward Reverse Moves |
| Square 11x11 at the border of the board, when the board is a half-plane | Center of the desert | 246 | Forward Reverse Moves |
| Square 11x11, when the board is the union of three half-planes tangent to the desert | Center of the desert | 241 | Forward Reverse Moves |
| Rhombus 13x13 (i.e. with axes of length 13) | Center of the desert | 58 | Forward Reverse Moves |
| Rhombus 15x15 (i.e. with axes of length 15) | Center of the desert | 176 | Forward Reverse Moves |
| Rhombus 15x15 at the border of the board, when the board is a diagonal half-plane | Center of the desert | 202 | Forward Reverse Moves |
| Rhombus 15x15, when the board is the union of three half-planes tangent to the desert | Center of the desert | 183 | Forward Reverse Moves |
