Solitaire Army, also known as Conway's Soldiers, is a mathematical game similar to peg solitaire. The setup is: you have an infinite peg solitaire board extending in all directions, and the starting position has a peg in every single position on the x-axis or south of it. In other words, every position (x,y) with y ≤ 0 contains a peg.
Legal moves are precisely those of peg solitaire: you may move a single peg exactly two spaces in any of the four orthogonal directions, provided the space it jumps over contains a peg and the space it ends up in is empty. The peg jumped over is removed.
The aim is to advance one peg as far north as possible, using up as many other pegs as you need to help get it there. Reaching y=1, for example, can trivially be done in one move; reaching y=3 is reasonably easy; reaching y=4 takes nearly twenty moves even with optimal play.
There is a well-
It occurred to me one day, however, that if we could somehow find a
way to make infinitely many moves, then the above proof
would stop being valid, and it might indeed be possible to reach the
fifth row by using up all the pegs on the entire infinite board.
And, indeed, this can be done. On this page I show how.
If we want to do this, we have to start by making sure we can
meaningfully define what it means to make infinitely many
moves on a peg solitaire board.
One obvious thing you could do would be to make a lot of moves
in parallel, if none of them interfered with each other.
For example, you could simultaneously jump every peg in the
y=−1 row two spaces upwards, thus removing all the pegs in
the y=0 row and completely filling the y=+1 row. This
would be an entirely well defined idea, but not particularly useful.
A more interesting possibility, though, is to make moves in an
infinite sequence, with each move depending on the result
of the previous one.
For example: suppose we started out with a line of pegs extending
off to infinity in one direction. We can clearly jump the second peg
in the line over the first one; then we can clearly jump the fourth
peg over the third into the space we've just made; then we can jump
the sixth over the fifth, and so on. Making any finite
number of moves from the start of this sequence would be perfectly
legal by the standard Solitaire Army rules.
But it's not too much of a stretch to imagine making all
the moves in that sequence, and going on forever. Doing so has the
property that each individual board position changes between empty
and full a small finite number of times; no position changes
infinitely often. So for each board position, we can meaningfully
talk about its eventual state: whether it ends up
with a peg in it or not after our move sequence finishes messing
about with it.
So what we would like to do is to allow ourselves to make all the
moves in the above sequence, leaving every peg in its eventual
state, and then make some more moves afterwards.
A nice way to make this rigorous is to imagine making all those
infinitely many moves during a finite space of time, by
acceleration. We make the first jump in the sequence at time
t=0; the second jump at t=1/2, the third at
t=3/4, the fourth at t=7/8, and so on. At t=1,
we have therefore made all the moves in the sequence, and yet we
haven't run out of time in which we can make more moves.
In this section I set up a more formal mathematical foundation for
the intuitive idea of infinite move sequences described in the
previous section. If mathematical notation scares you, you can
safely skip this section and move on to the next one, where you'll
find more actual infinite solitaire moves to scare you instead.
Formally speaking, my model is as follows. I define a function
f(x,y,t), with x,y
integers and t a real number, which gives the state of the
board position (x,y) at time t. The value of
f(x,y,t) is at all times either 0
(meaning there is no peg at that position), 1 (meaning there is a
peg), or 1/2 (meaning that t is the precise instant of a move
which changes the value of that position). The function f is
then subject to some constraints:
I won't go through the tedious details of proving that the
construction I've exhibited above satisfies all the constraints on
f (apart from the starting and ending ones), but a keen
reader shouldn't find it too difficult to do so.
The model I've defined here actually rules out my example of
parallel moves, in the precise form I exhibited it above.
The one-
Incidentally, a consequence of the rules as I state them above is
the following theorem:
I've given, above, an example of what I describe as a forward
infinite move sequence: a sequence of moves which has a clear
beginning, but no end, compressed into finite time so that we can
make more moves after it. I now give an example of a
backward infinite sequence: one with a clear end, but no
beginning.
Observe that in the formal definition of my rules all the
constraints I defined on my function are time-
Suppose, in reverse peg solitaire, we start out with a single peg
and we wish to turn it into infinitely many pegs. How might we do
this? Well, we have to start by making some move: let's jump our
starting peg to the left, turning it into two pegs. Suppose we then
jump the leftmost of those two pegs left again, turning that into
two pegs; and suppose we jump the leftmost peg left again, and keep
going. This gives us a forward-
And because every valid sequence in the reverse game can be
time-
This trick, for some reason, tends to make people's brains hurt.
People I've talked to seem to take the previous section in their
stride: they find it reasonably easy and intuitive to imagine
starting a sensible-
A particularly useful feature of the backward-
In the following section this doubly-
I've now described a move sequence which turns a semi-
A new concept that will be introduced in this section is the idea of
performing an infinite sequence of steps of which each step
contains several ‘whooshes’ as described in the previous section,
each of which in turn contains infinitely many moves. This isn't too
difficult: once we've got the idea of performing infinitely many
moves in a finite time, it's then reasonably simple to divide a
finite time into infinitely many intervals (e.g. one of length 1/2,
one of length 1/4, one of length 1/8, and so on), and then to
subdivide each of those intervals up into infinitely many parts as
well. This still doesn't break any of the rules I defined above:
every move still happens at a distinct instant of time, and no
square is filled or emptied infinitely often.
One obvious way to perform a megawhoosh, using that
idea, would be to whoosh every column of our
quarter-
But this, it turns out, isn't particularly useful. The single
resulting peg ends up two spaces inwards from the quarter-
So we need to do something rather different. I'm now going to
exhibit a more complicated but more useful megawhoosh:
one which consumes
the entire quarter-
This procedure is going to involve a large backwards-
We begin by moving our peg left. This first move gets us out of the
central column, and hereafter we will not touch the central column
at all.
Next, we whoosh these two pegs downwards, leaving two full columns
starting one space above the line. (Since we're currently playing
reverse solitaire, of course, the whoosh sequence is also performed
in reverse, converting one peg into a semi-infinite line of them
rather than vice versa. When we replay this forwards, it will become
a normal whoosh again.)
Now we move the top peg of the left column left:
Then we whoosh the resulting two pegs downwards again:
Now repeat those two steps with the top peg of the new left column:
Then keep repeating those two steps infinitely many times. Once we
finish that, we have a perfect staircase of pegs descending off to
the left:
(What we've just done is a forward-
Next we take every other peg on the outer edge of that
staircase, starting with the topmost one, and whoosh
them all to the left:
Now all we have to do is to move those alternating pegs downwards in
each column to fill in the gaps. This takes only a finite number of
moves in each column:
And we end up with a tightly packed quarter-
And that's our desired megawhoosh, in reverse. Run the
same sequence of moves in the forward direction, and we convert the
quarter-
Now that we have the whoosh and the
megawhoosh, the actual solution is quick to state:
Here's an animation of the entire solution run in the forward
direction. (It takes about 75 seconds to run fully, so if it's half
way through by the time you've read this far, wait a little while
and it'll start again.)
Gareth Taylor and I wrote up a more formal
article
containing the material on this page and some additional proofs and
discussion.
John
Horton Conway devised the original proof that y=5 cannot
be reached in finitely many moves; he may or may not have invented
the Solitaire Army problem itself.
Simon
Tatham had the idea of making a serious effort to reach
y=5 by means of making infinitely many moves; he laid down
the ground rules, invented the whoosh, and wrote this
web page.
Gareth Taylor named
the whoosh and invented the useful form of the megawhoosh,
completing the solution.
Basics
Making it mathematically rigorous
So we are after a function f which satisfies all of the above
constraints, and also has the property that at some time
t0 the board is in the starting position (in other
words, f(x,y,t0) is 1 if
y ≤ 0, and 0 otherwise), and at some later
time t1 > t0 there
is a peg in the fifth row
(f(x,5,t1)=1 for some x; in
fact, without loss of generality we may assume that x=0 and
that we're specifically heading for the point (0,5).)
for every time instant t
The interesting thing about this is that if I were to merely swap
round the second and third lines of the statement of that
theorem, so that a single value of ε had to work for all
(x,y), this would turn it into a constraint which
permitted only finitely many moves in any bounded time interval, and
hence we would have reverted to exactly the standard
definition of the game. This illustrates just how little I've had to
change the rules to permit infinite move sequences.
for every (x,y)
there exists some ε > 0 such that
within the time interval
(t−ε,t+ε)
the position (x,y) is not involved in any move which
is not at time t.
Another useful move
Further complication
The solution
Credits