The smallest army capable of moving forward eight rows, when diagonal jumps are allowed [P2].
These pages were created and are maintained by George Bell (gibell@comcast.net) Last Modified November 4th, 2024 Copyright © 2006–2023 by George I. Bell	To normal peg solitaire To triangular peg solitaire
... a good maths problem to do in your head when you don't want to think about something else because you can make it as complicated as you need to fill your brain by making the board as big as you want and the moves as complicated as you want. Mark Haddon, The Curious Incident of the Dog in the Night-Time [B3]

Table of Contents:

• Introduction
• Army types: Pablitos, Hexagonal, Skew, Diagonal
• Pagoda Functions
• Minimum Size Armies
• References

Introduction

The peg solitaire army problem is a one-player game played on an infinite board in which every square below a certain horizontal line is occupied by a peg (or "man"). It is also known by as "Conway's Soldiers". Play proceeds by jumping a man horizontally or vertically over another man into an unoccupied space, removing the jumped man. Surprisingly, no matter how the game is played, it is impossible for any man to advance more than four rows beyond the initial line.

The armies in the above diagram are capable of reaching their final goal, marked by an "X". It is relatively easy to discover the sequence of jumps that accomplishes this for the first three cases, but the right-most army to level 4 is harder to verify. The ghost men marked "B" represent an alternative to the men marked "A".

The above armies are also of the smallest possible size capable of reaching this target hole. Alternate armies reaching level 4 are shown below: a minimum size army, (20 men, left), and a symmetrical 21-man army (right). Already we can see there is a trade-off between army symmetry and the minimum size army capable of reaching a certain level.

Types of Army

The variations we will consider are:

1. Conway's army: Peg solitaire under the usual rules, allowing jumps only along rows and columns. First considered by John Conway in 1961. Analysis of the problem in Winning Ways for your Mathematical Plays, Vol 4 (2004 edition).
2. Skew army: Start from the usual position on a square lattice board, but allow only diagonal jumps.
3. Pablito's army: Peg solitaire on a hexagonal grid on a triangular board. Assemble an army on the lower part of a triangular board, with the top n rows empty. The goal is to jump pegs and finish with the last peg in the topmost hole. The problem was named and introduced as a Macalester College Problem of the Week.
4. Hexagonal Army: Like the previous, only we use an infinite board. We do not force the initial peg distribution to lie on a triangular board, with the finishing hole the top one. This version is equivalent to Conway's army with the addition of diagonal jumps in one direction only. This problem was considered by John Duncan and Donald Hayes [P1].
5. Diagonal army: Conway's army with diagonal jumps in both directions allowed. Considered by Aigner (1997) and Eriksen et. al. (2000).

Pagoda Functions

The following identities are useful in order to calculate the sum below a certain row. They are only valid for a σ that satisfies σ² + σ = 1.

1. Conway's:
   5 4 3 2 1 0 1 2 3 4 5
   6 5 4 3 2 1 2 3 4 5 6
   7 6 5 4 3 2 3 4 5 6 7
   8 7 6 5 4 3 4 5 6 7 8
   9 8 7 6 5 4 5 6 7 8 9
   

   Sum of row n and beyond:
   S_n¹ = σ^n-5
   Highest level that can be reached: 4 (see table below)

2. Skew:
   5 4 3 2 1 0 1 2 3 4 5
   5 4 3 2 1 1 1 2 3 4 5
   5 4 3 2 2 2 2 2 3 4 5
   5 4 3 3 3 3 3 3 3 4 5
   5 4 4 4 4 4 4 4 4 4 5
   

   Sum of row n and beyond:
   S_n² = σ^n-4(2σ³ + nσ²+1) = σ^n-3((n-1)σ+3)
   Highest level that can be reached: 6 (see table below)

   Again this pagoda function is particularly simple, and all upward jumps lose nothing. Any horizontal jump loses an amount equal to the hole jumped over, and any downward jump loses twice this amount. The best solutions involve almost exclusively upward jumps.

3. Pablito's:
       0
      1 1
     2 2 2
    3 3 3 3
   4 4 4 4 4
   

   Sum of row n and beyond:
   S_n³ = σ^n-4(nσ² + 1) = σ^n-3((n+1)σ+1)
   Highest level that can be reached: 6 (see table below)

   This version has a particularly simple pagoda function. Note that any upward jump loses nothing in regard to this pagoda function. Any horizontal jump loses an amount equal to the hole jumped over, and any downward jump loses twice this amount. The best solutions involve almost exclusively upward jumps.

4. Hexagonal Grid:
   5 4 3 2 1 0 1 2 3 4 5
    5 4 3 2 1 1 2 3 4 5
   6 5 4 3 2 2 2 3 4 5 6
    6 5 4 3 3 3 3 4 5 6
   7 6 5 4 4 4 4 4 5 6 7
   

   Sum of row n and beyond:
   S_n⁴ = σ^n-4(nσ² + 2σ + 1) = σ^n-3((n+1)σ+3)
   Highest level that can be reached: 7 (see table below)

5. Fully Diagonal:
   5 4 3 2 1 0 1 2 3 4 5
   5 4 3 2 1 1 1 2 3 4 5
   5 4 3 2 2 2 2 2 3 4 5
   5 4 3 3 3 3 3 3 3 4 5
   5 4 4 4 4 4 4 4 4 4 5
   

   Sum of row n and beyond:
   S_n⁵ = σ^n-5(2nσ³ + 2σ² + 1) = σ^n-5((4n-2)σ + 3-2n)
   Highest level that can be reached: 8 (see table below)

The table below shows the value of the sums S_nⁱ for various values of n and i, showing the highest level that can be reached.

n	Sn1	Sn2	Sn3	Sn4	Sn5
1	6.8541	7.8541	5.8541	11.0902	15.3262
2	4.2361	5.8541	4.6180	7.8541	11.4721
3	2.6180	4.2361	3.4721	5.4721	8.3262
4	1.6180	3.0000	2.5279	3.7639	5.9098
5	1.0000	2.0902	1.7984	2.5623	4.1246
6	0.6180	1.4377	1.2574	1.7295	2.8409
7	0.3820	0.9787	0.8673	1.1591	1.9361
8	0.2361	0.6606	0.5917	0.7721	1.3081
9	0.1459	0.4427	0.4001	0.5116	0.8773

Minimum Size Armies

n	Minimal Army Size
	Conway's A014225	Skew	Pablito's	Hexagonal grid A014227	Fully diagonal A125730
1	2	2	2	2	2
2	4	3	3	3	3
3	8	5	5	5	5
4	19 ≤ 20	9 ≤ 9	9 ≤ 9	9 ≤ 9	7 ≤ 8
5	Impossible	18 ≤ 19	18 ≤ 19	16 ≤ 17	13 ≤ 13
6		43 ≤ 46	51 ≤ 53	35 ≤ 36	23 ≤ 23
7	Impossible			140 ≤ Size ≤ 145, 149 156 Duncan & Hayes (1991)	45 ≤ 46
8	Impossible				122 ≤ 123
≥ 9	All Impossible
Notation: Lower Bound ≤ Optimal Value ≤ Upper bound The lower bound comes from a pagoda function. The upper bound is the best known solution.

As an example of an army in action, the following diagram shows a 19-man Pablito's army reaching 5 steps forward. This diagram, and all armies in action, can be viewed by clicking on the appropriate entry in the table above.

The table below shows minimal armies divided into "regiments". For example, all the red men form a regiment which is capable of reaching the top hole colored red. The red and blue men are usually mirror images of one another. The final hole to be reached is marked by an X. Sometimes it is the case that one regiment must move before the others. Note that the army diagrams presented above do not necessarily proceed forward by regiment. In general, there are many ways that a specific army can move forward to reach its final target hole.

n	Minimum Army Size
	Skew	Pablito's	Hexagonal grid	Fully diagonal
4	9   ⇒
5	19   ⇒
6	46
7	Impossible
8	Impossible
≥ 9	All Impossible
Notation: Lower Bound ≤ Optimal Value ≤ Upper bound The lower bound comes from a pagoda function. The upper bound is the best known solution.

The minimum army size needed to reach level n can be found in The On-Line Encyclopedia of Integer Sequences as A014225. The same question for a hexagonal lattice generates A014227.

Peg Solitaire Army References

Books

Papers

Web References

Copyright © 2006–2014 by George I. Bell

To square lattice peg solitaire    To triangular lattice peg solitaire    Home