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.
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.
A
B
C
D
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.
Count
(mod 3)
A
xx
yy
B
xx
yy
C
xx
yy
D
xx
yy
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
A legal move can only change the counts by +3 or -3,
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:
The remainders of the four counts (mod 3) never change.
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:
It is impossible to play Figure 1 to a single counter in the center.
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:
Figure 1 can finish with a counter at c1, a3, e3 or c5, but no other squares.
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.
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:
Choose any square on the board (call it "S") and mark it with a 1.
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.
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,
The mod 3 invariants (for a given board) form a vector space.
It is not difficult to show that, as long as the board is
reasonably connected,
The space of mod 3 invariants is 4-dimensional.
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.