The Peg Solitaire Army 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 February 24th, 2014 Copyright © 2006–2014 by George I. Bell 


... 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 NightTime [B3] 
The peg solitaire army problem
is a oneplayer 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 rightmost 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 21man army (right).
Already we can see there is a tradeoff between army symmetry and the
minimum size army capable of reaching a certain level.
The variations we will consider are:
The following identities are useful in order to calculate the sum below a certain row.
They are only valid for a σ that satisfies
σ^{2} + σ = 1.
Sum of row n and beyond:
S_{n}^{1} = σ^{n5}
Highest level that can be reached: 4 (see table below)
Sum of row n and beyond:
S_{n}^{2} = σ^{n4}(2σ^{3} + nσ^{2}+1)
= σ^{n3}((n1)σ+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.
Sum of row n and beyond:
S_{n}^{3} = σ^{n4}(nσ^{2} + 1)
= σ^{n3}((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.
Sum of row n and beyond:
S_{n}^{4} = σ^{n4}(nσ^{2} + 2σ + 1)
= σ^{n3}((n+1)σ+3)
Highest level that can be reached: 7 (see table below)
Sum of row n and beyond:
S_{n}^{5} = σ^{n5}(2nσ^{3} + 2σ^{2} + 1)
= σ^{n5}((4n2)σ + 32n)
Highest level that can be reached: 8 (see table below)
The table below shows the value of the sums S_{n}^{i} for various values of n and i, showing the highest level that can be reached.
n  S_{n}^{1}  S_{n}^{2}  S_{n}^{3}  S_{n}^{4}  S_{n}^{5} 

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 
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 19man 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 OnLine Encyclopedia of Integer Sequences as A014225. The same question for a hexagonal lattice generates A014227.
B1.  John D. Beasley, The Ins & Outs of Peg Solitaire, Oxford Univ. Press, 1985 (the paperback Edition 1992, contains an additional page: Recent Developments) ISBN 019286145X (paperback).  
B2.  John H. Conway, Elwyn R. Berlekamp, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 4, AK Peters, 2004 (second edition).  
B3.  Mark Haddon, The Curious Incident of the Dog in the NightTime, Vintage, 2004. 
P1.  John Duncan and Donald Hayes, Triangular Solitaire, Journal of Recreational Mathematics, 1991, Vol 23, p. 2637.  
P2.  George I. Bell, Dan Hirschberg and Pablo Guerrero, The minimum size required of a solitaire army, INTEGERS Electronic Journal of Combinatorial Number Theory, Vol 7, G7, 2007.  
P3.  George I. Bell, The shortest game of Chinese Checkers and related problems, INTEGERS Electronic Journal of Combinatorial Number Theory, Vol 9, G1, 2007. This paper considers what happens when the rules are changed so that a man is not removed by a jump. These are the same rules used in the game of Chinese Checkers. Clearly, any level can now be reached, so the interesting question is how quickly can one get an army from one place to another (transfer a set of men in the smallest number of moves). 
W1.  Eric Weisstein has a page on mathworld.wolfrom.com.  
W2.  Mathematical Mysteries: The Solitaire Advance, Plus Online Maths Mag. Issue 12, Sept. 2000.  
W3.  "Pablito's Solitaire" was the Macalester College Problem of the Week (#860, Spring 1998 and #981, Spring 2003).  
W4.  Home page of Pabl(it)o Guerrero García, contains some preprints of Pablo's papers.  
W5.  The OnLine Encyclopedia of Integer Sequences, see sequences A014225, A014227, and A125730.  
W6.  Stephen Hartke has studied the problem in reverse, i.e. starting with one man and moving him down to form an army. In this paper he and Pieter Blue consider the puzzle where an infinite number of jumps are allowed.  
W7.  Simon Tatham has also considered the puzzle where the number of jumps can be infinite. He shows how Conway's Army can reach level 5 in this infinite setting. 
Copyright © 2006–2014 by George I. Bell