1 2

Port-and-Sweep Solitaire

An interactive guide


Impossibilities

The puzzle in Figure 1 can be played to a single counter in the middle of one of the edges (cells c1, a3, e3, or c5) without much difficulty — try it! For symmetry, it would be more satisfying to leave the last counter in the center, and for variety, it might also be interesting if any other finishing squares were possible.

But no, only the edge-middle squares are possible. Certain quantities are conserved throughout the course of play, even as the number and positions of the counters change. These invariant quantities will make it easy to rule out any other possible finishes for this puzzle.

abcde 12345 Reset board to initial state

Figure 1

You can play to a single counter, but which squares can it finish in?
Can you finish in the center?

Place Values and Counting

Figure 2 gives place-value diagrams to define four count functions for game positions on the 5×5 board.

The leftmost diagram in Figure 2 shows the place-values for the A count. To evaluate the A count for a game position, multiply each place-value by the number of counters in the corresponding square of the game position, and add up the results. (The idea is easier to express in terms of vector arithmetic: just regard the place-value diagram and the game position as two vectors, and dot them together.)

The remaining place-value diagrams in Figure 2 define the B, C, and D counts.

Try it out: Figure 3 recaps the position from Figure 1, together with the values of the four counts. As you make moves, the values will automatically update to reflect the new position.

212121212 122112 121212 1221
ABCD

Figure 2

Place value diagrams for the A, B, C, and D counts. Multiply by the number of counters in the corresponding square of your game, then add up to get the total count. These totals can only change by plus or minus three under legal moves.

Reset board to initial state
Count(mod 3)
Axxyy
Bxxyy
Cxxyy
Dxxyy

Figure 3

Counts can change, but remainders (mod 3) never do.

Invariants: Remainders (mod 3)

Figure 3 demonstrates that the A, B, C, and D counts can vary as you make moves. However, you may notice that

and it's easy to prove that this observation is correct (the most direct way is just to check all possible moves). That means we have four invariant quantities:

Let us call that list of four remainders the (A,B,C,D) invariants, or just the invariants, for brevity. In Figure 1, the invariants are initially (1,0,0,0), and every position you could ever reach in Figure 1 must have the same values.

Now, imagine a position with a single counter in the center square. The invariants for that position would be (2,0,0,0). Thus:

Not only that, the invariants for a single counter at, say, b1, would be (0,1,0,0), so that is ruled out as a finishing square too. In fact, the invariants rule out all possible finishing squares except c1, a3, e3, and c5. On the other hand, just by playing, you can demonstrate that these four are all possible (and if any one of them is possible, then by symmetry, all of them are, so one solution is all that's needed). In summary:

Although the 5×5 board allows for many interesting, compact puzzles, we can see now that it does not allow complement problems. Taking one counter away from every square on the board changes the mod 3 value of the A-count (adding one to it, mod 3). That cannot be achieved be any sequence of legal moves.

Interlude: Puzzles

Figure 4 has four puzzles which play to a single counter at various locations on the board. It's not strictly necessary, but the (A,B,C,D) invariants will help determine the possible finishing squares.

You can simplify the calculation by playing each board down to a position with few counters first. Since the invariants don't change, you'll get the same values for the simplified position as for the starting position, but with much less work.

Another useful simplification is that two counters a port move away from each other (for example, one at a1 and one at a3) cancel each other mod 3, and can be ignored in calculating the invariants.

Reset board to initial state Reset board to initial state Reset board to initial state Reset board to initial state

Figure 4

Play to a single counter in various locations.
The invariants can help predict the possible finishing squares.

Another Viewpoint

In Math Horizons [1], I present the same invariants in a different way, taking advantage of the additive and multiplicative structures in a finite field of nine elements (which is explained in the article). That makes it particularly simple to confirm that the invariants really are unchanged by all possible port and sweep moves, without checking a lot of cases. The finite field definition of the invariants can also be applied to boards of any size and shape, without modifications. Very tidy!

When I play or analyze puzzles, however, I do not think of arithmetic in the field of nine elements, but in terms of the four counts, and their remainders, as I have defined them here. The two viewpoints are equivalent, and one can use whichever is most convenient in a particular context.

Invariants on Other Boards

You can construct place-value diagrams like Figure 2 on any board:

  1. Choose any square on the board (call it "S") and mark it with a 1.
  2. Visit all squares that can be reached from S by port moves, and mark them alternately with 2s and 1s (by "alternately", I mean that two squares that are a port move apart should have different values).

On almost any board that would be interesting to play on, you can do this four times (with four different starting squares) to get four different and independent place-value diagrams. The corresponding count functions can only increase or decrease by multiples of 3 as you play, so the remainders mod 3 will be invariant, just as on the 5×5 board.

Figure 5 shows four invariants obtained in this way for the 25-square diamond board. You can apply these to help deduce the possible finishing squares for the 25-square diamond problems on Page 1, if you haven't already done so.

On the 25-square diamond, the position with one counter in each square has invariants (0,0,0,0); equivalently, modifying a position by taking one counter away from each square does not change the invariants.

1121111212122
121212121221

Figure 5

Place values defining four invariants (mod 3) on the 25-square diamond.

Are There Any Other Interesting Mod 3 Invariants?

This section assumes familiarity with linear algebra.

As mentioned above, we can view a place-value diagram and a board position as two vectors which can be dotted together. For now, let us view them specifically as vectors over the field of integers mod 3.

We can also view moves as vectors, which are added to a position to change it. A place-value diagram represents an invariant if and only it gives 0 when dotted with every move vector. Or, in other words, the mod 3 invariants for a given board are precisely the nullspace of a large matrix whose rows are the legal move vectors on the board. Consequently,

It is not difficult to show that, as long as the board is reasonably connected,

If you choose a 2×2 square on the board and apply the method of the previous section to each of the four cells, you get four linearly independent invariants, which consequently form a basis for the space of all invariants. No other mod 3 invariants will give any information that isn't already revealed by the four you have constructed.

Port-and-Sweep was specifically designed with mod 3 arithmetic at its heart, as an algebraic variation of the traditional peg solitaire game, which has mod 2 arithmetic at its heart in much the same way [2]. That is why this page has discussed only mod 3 invariants. There are a few things to say about port-and-sweep invariants over other fields, but for the time being, I will leave that topic for you to explore on your own, as well as the precise meaning of the phrase "reasonably connected," as used above. For the curious and interested, it is also worth exploring counts that are invariant under sweeps, but not necessarily under ports.

References and Links

  1. Siehler, J. (2010), Port-and-Sweep Solitaire [PDF], Math Horizons, 18:1, 22-25
  2. Bell, G. (2016), George's Peg Solitaire Page ("Position Class and Null-Class Boards")