In the game of Peg Solitaire [1], pieces (or pegs) occupy some of the holes arranged in a square grid. The game begins with one empty position, and the objective is to remove all but one peg.
A legal move consists of jumping a peg over another peg in an orthogonally adjacent position, landing in the position immediately beyond it, which must be empty before the move. The jumped-over peg is removed from the board.
In an infinite version of the game, we can consider the integer lattice ℤ², where the origin (0,0) is initially empty and every other position is occupied.
Naturally, we do not have infinite time to perform all the required moves. The solution presented here is a mathematical construction that uses infinite sequences of moves completed within finite time intervals.
The construction is arranged so that there exists a natural number N, independent of the position chosen, that bounds the number of moves in which any given position participates. Furthermore, each move is assigned its own time interval, which may be arbitrarily short, allowing infinitely many moves to take place within a finite amount of time.
We will use an operation capable of eliminating all pegs along an infinite ray of occupied positions, leaving a single peg two units beyond the ray’s initial endpoint.
This operation is described and named a whoosh in [2]. In a whoosh, each position participates in at most two moves.
A whoosh consists of two parts. The first is a sequence of moves with a well-defined beginning, whose times approach a limit. In the second part, the moves occur in reverse order, as though a peg were coming from infinity and successively jumping over the others. This second part has a last move but no first move.
We can also eliminate infinitely many such rays arranged in distinct rows or columns by successively applying whooshes. This allows us to manipulate infinite two-dimensional regions, such as a quadrant of the plane.
To perform these operations within a finite amount of time, we can distribute the whooshes over successive time intervals. For example:
From t = 0 to t = 1/2, we eliminate the first ray.
From t = 1/2 to t = 3/4, we eliminate the second.
From t = 3/4 to t = 7/8, we eliminate the third.
And so on.
The durations of these intervals form a geometric progression with first term 1/2 and common ratio 1/2, whose sum is 1.
This is the same general idea used in the operation called a megawhoosh in [2], although we do not use it here in exactly the form presented in that paper.
This text does not attempt to provide a complete formalization of these infinite operations, known as supertasks. For their mathematical foundations, we refer the reader to [2].
Our objective is to present a construction consisting of only 16 steps, using these operations to solve Infinite Peg Solitaire.
The peg at (2,0) jumps over the peg at (1,0), landing at (0,0) and removing the jumped-over peg.
This is an ordinary Peg Solitaire move.
We apply a whoosh to the ray (−∞…0, 0), removing all its pegs.
In the notation used here, (−∞…0, 0) denotes the set of positions with y-coordinate zero and x-coordinate less than or equal to zero.
After this operation, the only occupied positions in that row are (2…+∞, 0).
We apply another whoosh, this time to the ray (2…+∞, 0).
At the end, only one peg remains at the origin (0,0), and every other position in the row y = 0 is empty.
We perform upward jumps with all pegs at positions (−∞…−1, −2) and (1…+∞, −2).
Each peg jumps over the peg immediately above it, landing in the position with y-coordinate zero in the same column.
As a result, rows y = −2 and y = −1 become empty, except for positions (0,−2) and (0,−1), which remain occupied. Row y = 0 becomes completely filled.
These two empty rows will allow us to apply whooshes in the next step.
To perform the infinitely many jumps within finite time, we use the following schedule:
From t = 1 − 2⁰ to t = 1 − 2⁻¹: move the peg at (1,−2) to (1,0).
From t = 1 − 2⁻¹ to t = 1 − 2⁻²: move the peg at (−1,−2) to (−1,0).
From t = 1 − 2⁻² to t = 1 − 2⁻³: move the peg at (2,−2) to (2,0).
From t = 1 − 2⁻³ to t = 1 − 2⁻⁴: move the peg at (−2,−2) to (−2,0).
We continue indefinitely, alternating between the two sides and increasing the distance from the origin.
At the end of the supertask, the entire row y = 0 is occupied.
We apply whooshes to all upward infinite rays starting at y = 0, in columns whose x-coordinate is not zero.
In our notation, this corresponds to:
(−∞…−1, 0…+∞) ∪ (1…+∞, 0…+∞)
We can perform these infinitely many whooshes within finite time, similarly to the previous step:
From t = 1 − 2⁰ to t = 1 − 2⁻¹: eliminate (1, 0…+∞), leaving a peg at (1,−2).
From t = 1 − 2⁻¹ to t = 1 − 2⁻²: eliminate (−1, 0…+∞), leaving a peg at (−1,−2).
From t = 1 − 2⁻² to t = 1 − 2⁻³: eliminate (2, 0…+∞), leaving a peg at (2,−2).
From t = 1 − 2⁻³ to t = 1 − 2⁻⁴: eliminate (−2, 0…+∞), leaving a peg at (−2,−2).
We continue alternating between columns to the right and left of the origin.
At the end, the entire row y = −2 is occupied.
In the following steps, we will no longer specify the time intervals, since the supertasks involved will be either individual whooshes or operations analogous to those already described.
We apply whooshes to the vertical rays (1…+∞, −∞…−2), removing all their pegs.
Each ray leaves one peg in row y = 0, forming the set (1…+∞, 0).
Since the origin (0,0) was already occupied, we obtain the fully occupied ray (0…+∞, 0).
We apply a whoosh to the ray (0…+∞, 0).
At the end, a single peg remains at (−2,0), and every other position in row y = 0 is empty.
The peg at (0,−2) jumps upward over the peg at (0,−1), landing at (0,0) and removing the jumped-over peg.
We apply a whoosh to the vertical ray (0, 0…+∞), leaving a single peg at (0,−2).
The positions (0, −∞…−3) remain occupied.
We apply whooshes to two vertical rays:
(−1, −∞…−2), leaving a peg at (−1,0).
(0, −∞…−2), leaving a peg at (0,0).
The peg at (−1,0) jumps to the left over (−2,0), landing at (−3,0) and removing the jumped-over peg.
We apply a whoosh to the ray (−2, −∞…−2), leaving a single peg at (−2,0).
The peg at (−3,0) jumps to the right over (−2,0), landing at (−1,0) and removing the jumped-over peg.
The peg at (0,0) jumps to the left over (−1,0), landing at (−2,0) and removing the jumped-over peg.
We apply whooshes to all vertical rays (−∞…−3, −∞…−2).
The pegs along these rays are removed, leaving one peg in row y = 0 in each corresponding column.
We thus obtain the occupied ray (−∞…−3, 0), which, together with the peg already present at (−2,0), forms the ray (−∞…−2, 0).
Finally, we apply a whoosh to the ray (−∞…−2, 0).
All its pegs are removed except one, which ends up at the origin (0,0).
The infinite board now contains exactly one peg. The puzzle is solved.
We have presented a 16-step construction that solves Peg Solitaire on an infinite board initially occupied at every position except the origin.
The solution uses operations involving infinitely many moves, arranged within finite time intervals. Although some steps involve infinite two-dimensional regions, their operations can be organized into countable sequences of supertasks while maintaining a uniform bound on the number of moves in which any given position participates.
In this way, we obtain a finite sequence of mathematically defined transformations that reduces the initial configuration to a single peg.
This solution was independently developed on January 6, 2022, by José Eduardo Gaboardi de Carvalho. An illustration of the construction is available in [3].
[1] Peg solitaire. https://en.wikipedia.org/wiki/Peg_solitaire
[2] TATHAM, Simon; TAYLOR, Gareth. Reaching Row Five in Solitaire Army. https://tartarus.org/gareth/maths/stuff/solarmy.pdf
[3] CARVALHO, José Eduardo Gaboardi de. Infinite Peg Solitaire. https://dudz.com.br/infinite-peg-solitaire/