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:
for every time instant tThe 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.
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.