As we saw in the previous section, solving peg solitaire using backtracking is fairly easy. In the following we will see why this is the case: There are so many solutions that it’s hard not to stumble upon them while mindlessly trying all possible moves. How many solutions are there exactly? Let’s find out.
We start with a simple variation of the backtracking algorithm used in the previous section, except that we now count the solutions instead of printing them:
int countSolutions(current) {
if (current == FINAL_BOARD) {
return 1
} else {
int n = 0
for (next : boards reachable from 'current' in a single jump)
n += countSolutions(next)
return n
}
}
The function returns the number of solutions that are reachable from current. If current is itself the solution, countSolutions() returns 1. Otherwise, it counts the number of solutions that start with one of the possible next jumps and then returns their sum.
Unfortunately, peg solitaire has so many solutions that this simple version of countSolutions() doesn’t complete in any reasonable amount of time. To make the problem more tractable, we will use two techniques: normalization, which simplifies computations by choosing a single, unique representation for game states that are equivalent; and memoization, which is a general method for speeding up recursive computations by tabulating the results of previous computations. Let’s see how they work and why they are so effective in this case.
Normalization
Many puzzles have symmetries we can exploit to reduce the number of moves or alternatives we have to consider. This is also true for peg solitaire. For example, the four different boards that can be reached with the first jump (shown in the second level of the tree in
Fig. 6.5) differ only in their orientation, so each of them must lead to the same number of solutions. We can therefore speed up countSolutions() by choosing one of the possible four jumps in the first step, computing the resulting
number of possible solutions, and then returning four times this number — without investigating the other three possible jumps at all.
It’s easy to generalize this idea to any board configuration. We first note that rotation isn’t the only kind of symmetry we can exploit: All boards that can be obtained by rotation, vertical or horizontal reflection, or any combination thereof have the same number of solutions, provided we are searching for a
solution with the final peg in the center of the board. As illustrated in Fig. 6.6, this gives us a maximum of eight configurations that can be considered equivalent: the four rotations we already discussed and their reflections. (Both
horizontal and vertical reflections produce the same four states in the bottom row, albeit in a different order.)
Figure 6.6 .
]Symmetries in peg solitaire. In a standard peg solitaire game, all eight boards shown here are equivalent in the sense that they lead to solutions that differ only in their orientation.
The idea behind normalization is to choose a unique instance from the eight configurations in Fig. 6.6, thereby making it easier to detect boards that have already been investigated. For boards that are stored
as bit sets, the easiest way to choose a unique representative is to compute the minimum of the corresponding integers. The normalize() method in Listing 6.6 performs this normalization by rotating and mirroring a given bitboard in all possible ways and keeping track of the one that is numerically smallest. In our case, the numerically smallest bitboard is the one with
holes at the largest indices; in Fig. 6.6 this is the board in the lower right.
Listing 6.6ch6 / PegCount
// Map 'board' to a unique representative from all equivalent
// rotated and flipped boards.
static long normalize(long board) {
long result = Math.min(board, flipH(board));
long rot90 = rotate(board);
result = Math.min(result, Math.min(rot90, flipH(rot90)));
long rot180 = rotate(rot90);
result = Math.min(result, Math.min(rot180, flipH(rot180)));
long rot270 = rotate(rot180);
result = Math.min(result, Math.min(rot270, flipH(rot270)));
return result;
}
To implement rotate() and flipH(), we first note that both operations can be described by
moving each bit to a new position. We use two arrays to specify the new positions of each bit (Listing 6.7): FLIP_H mirrors each row
of the board horizontally and ROTATE rotates it counterclockwise. The \(k\)th entry in each array indicates the target position of the \(k\)th peg. After defining these permutation tables, we reorder the
bits by calling shuffleBits(), which is defined in Listing 6.8.
// Reorder bits by moving each one to a new position.
private static long shuffleBits(long bits, byte[] targetIndex) {
long result = 0L;
for (int i : Bits.iterate(bits))
result |= Bits.bit(targetIndex[i]);
return result;
}
What do we do with the normalized boards we just constructed? This is where the second technique, memoization, comes in.
Memoization
Memoization is a programming technique for speeding up expensive functions by caching the results from previous calls in an auxiliary data structure. Effectively, memoization is a method for tabulating a given function on demand: we don’t have to know
beforehand which function arguments actually occur in practice but simply tabulate those that do occur when they occur.
Memoization can be used for both recursive and non-recursive functions. If F is a non-recursive function that depends on a single parameter x, we can create a memoized version of this function by wrapping it in a new function memoizeF that uses an auxiliary
data structure cache to quickly return the results of previous calls without repeating the actual computation:
memoizeF(x) {
if (!cache.contains(x))
cache[x] = F(x)
return cache[x]
}
If cache already contains a value for the argument x it is returned directly; otherwise, the original function F(x) is called and cache is updated with the result.
For recursive functions, we have to interleave the memoization logic with the implementation of the recursive function. It’s easiest to see how this works by considering a concrete example. The factorial function \(n!\) is defined recursively as
\(\seteqnumber{0}{6.}{1}\)
\begin{align*}
0! &= 1\\ n! &= n\cdot (n-1)!
\end{align*}
To implement a memoized version of this function, we first define a hash map cache to store previous results and then define a factorial() method as shown in the following listing:
static HashMap<Integer, Integer> cache = new HashMap<>();
static int factorial(int n) {
if (n == 0) // base case
return 1;
if (!cache.containsKey(n))
cache.put(n, n * factorial(n - 1));
return cache.get(n);
}
As you can see, the memoized version of a recursive function is still recursive, but redundant function calls are avoided by caching previous results.
In principle, memoization be used with any pure function, that is, a function whose return value depends only on its arguments and that doesn’t have any side effects. In addition, memoization works best if the function is sufficiently expensive to
compute and if it is called repeatedly with the same arguments: There is little value in tabulating simple arithmetic expressions or functions that are called only once. The main downside of the technique is that that the tables produced by memoization can consume a significant amount of memory.
Let’s see how to use memoization to speed up the countSolutions() function for counting the solutions of peg solitaire. Both prerequisites mentioned above are satisfied: The function is expensive to compute (at least for boards that contain more than a
handful of pegs) and the same boards are evaluated over and over again, both naturally (because there are often several different sequences of moves that lead from one board to another), and even more so if we also use normalization to merge game states that are considered equivalent. To implement
memoization, we use a hash table that maps boards (long integers in bit representation) to the number of possible solutions (because this number can grow large, we use long integers here as well). The resulting implementation of countSolutions() is shown in
Listing 6.9.
Listing 6.9ch6 / PegCount
private static HashMap<Long, Long> numSolutions = new HashMap<>();
public static long countSolutions(long board) {
if (board == FINAL_PEGS)
return 1;
long normalized = normalize(board);
if (numSolutions.containsKey(normalized)) {
return numSolutions.get(normalized);
} else {
long n = 0;
for (int movable : Bits.iterate(movablePegs(board))) {
var holes = reachableHoles(board, Bits.bit(movable));
for (int hole : Bits.iterate(holes))
n += countSolutions(jump(board, movable, hole));
}
numSolutions.put(normalized, n);
return n;
}
}
On the author’s computer, the function completes in just a few minutes. The result? For the standard peg solitaire board there are 40 861 647 040 079 968, or approximately 41 quadrillion, unique solutions.
This raises an interesting questions: If solutions are so plentiful, why do human players still find peg solitaire moderately difficult? The main reason is (ironically) that the number of solutions is only 41 quadrillion — a tiny number compared to the vast
number of possible ways to play the game. As we will discuss in Exercise 6.6, most boards that are reachable from the starting configuration are unwinnable. If you play peg solitaire without some kind of strategy, you are therefore
likely to end up in a dead end.
Exercises
Exercise 6.5. Estimate how long it would take a modern computer to generate all 41 quadrillion solutions of peg solitaire.
Exercise 6.6. How many distinct boards does the call
Exercise 6.8.The interface Function defined in Java’s standard library represents a general function from
values of type T to values of type R. Write a class Memoizer that “memoizes” a given non-recursive Function by wrapping it and caching all return values. For example, the following listing creates a memoized version
of the function v -> v.toString() that converts integers to their string representation:
var f = new Memoizer<Integer, String>(v -> v.toString());
assert f.apply(1).equals("1");