Countless variations of peg solitaire can be obtained by changing the geometry of the board and the initial and final positions of the pegs [40, 11]. New and interesting questions also arise if we shift our focus from individual jumps to sequences of jumps. For instance, if we treat successive jumps with a single peg as a single move, how many such moves are
necessary to clear the entire board? The answer is 18, and finding the corresponding solution is left as an exercise for the reader.
This chapter was inspired by an article by Bell [12]. There are also strategies for solving peg solitaire that do not rely on trial and error or brute computational force; for an overview, see the book
by Berlekamp et al. [15, Chapter 23].
Problems that involve searching or analyzing arrangements of objects are called combinatorial problems. Sometimes the goal is to find a certain specimen among all possible arrangements, for example when playing the lottery or trying to crack a combination lock. Other times, we consider the entirety of arrangements: How
many different solutions does peg solitaire have, or what is the total number of different chess games?
Our discussion of peg solitaire highlighted an issue that plagues many combinatorial problems: Small instances of the game are easy to analyze, but as we increase the number of pegs, the number of possible solutions grows so quickly that it becomes impossible to generate them all using “brute force.”
This phenomenon is known as combinatorial explosion, and it occurs in almost every situation in which we investigate arrangements of objects. Whenever there is more than one way to choose an object for each position in the arrangement, the total number of combinations
grows at least exponentially, quickly outpacing the capabilities of even the most powerful computers.
The extraordinary speed of exponential growth is illustrated in Fig. 6.8. The lower four curves are growth rates that are commonly encountered in computer science. As the size of \(n\) increases along the horizontal axes, these functions
show a moderate growth. (Both axes are logarithmic so the quadratic growth \(n^2\) appears as a line.) In contrast, the growth of the exponential function \(2^n\) is constantly accelerating and quickly reaches astronomical values.
Figure 6.8 Comparison of growth rates. Exponential functions grow so quickly that they quickly reach astronomical values.
We used bitboards to represent the different configurations of pegs and holes in peg solitaire. Similar techniques can be used in many other puzzles that involve the placement or movement of pieces on a board. A natural example is chess, where the 64 squares of the board naturally map to the 64 bits of a long integer. A slight complication in this case is that chess pieces come in two colors and six different types: kings, queens, rooks, bishops, knights, and pawns. If we use one bitboard
for each type of piece, we can represent the complete state of a chessboard using twelve bitboards. Bitwise techniques can the then be used to quickly perform many important operations, such as computing possible moves or checking which pieces threaten other pieces. A popular open-source chess
engine that uses bitboards is Stockfish (https://stockfishchess.org/). For a survey of bitboard techniques similar to the ones discussed in this chapter, see the article by Browne [21].
The game Nim, which we discussed in Exercise 6.9, was first described in 1901 by the American mathematician Charles L. Bouton [19]. Nim is one of the simplest examples of what mathematicians call a combinatorial game, a two-player game that doesn’t involve chance and in which both players have complete information about the state of the game. Other popular examples of combinatorial games are tic-tac-toe, Connect 4, checkers, and
chess. For every combinatorial game, we can ask whether there is a winning strategy that guarantees a victory even if the opponent plays optimally. In the paper cited above, Bouton showed that there is an optimal strategy for playing Nim. The field of combinatorial game theory extends this analysis to a wide range of other games [3].
We saw that the winning strategy for Nim can be implemented using just a few XOR operations, which made it possible to construct Nim-playing machines several years before the development of electronic computers. The first such machine
was the Nimatron, a massive electro-mechanical device that was showcased at the World’s Fair in New York in 1940, where it managed to win 90 % of the 100 000 games it played [80].
The main technique we used to solve combinatorial problems in this chapter was backtracking, which tries all possible steps or moves until it happens upon a suitable solution. Modern computers are so fast that backtracking alone can solve most simple combinatorial puzzles, but if the number
of possible moves grows too large, the number of potential solutions becomes prohibitive and more sophisticated algorithms must be tried to reduce the amount of trial-and-error required.
In the case of Sudoku, two approaches are especially noteworthy. Both convert each Sudoku puzzle into a constraint satisfaction problem (CSP), which consists of a set of variables whose values we wish to determine (in our case, the numbers in the squares of the Sudoku board) and a set of constraints those variables must satisfy (which include both
the rules of the game and the existing numbers on the board).
One algorithmic technique for solving or at least simplifying such problems is known as constraint propagation [72]. This approach resembles the way humans solve Sudoku puzzles: If we know the number in a particular square, we can “propagate” this
knowledge to constrain the range of allowed numbers of other squares in the same row, column, and block; we then repeatedly propagate these new constraints in the same way.
The second approach is to translate the problem into a Boolean formula and then search for a set of variables that satisfies this formula. Let’s use the variable \(x_{ijk}\) to indicate that the square in row \(i\) and column \(j\) has value \(k\) and its negation \(\bar
x_{ijk}\) that the value is not \(k\). With this convention, we can encode the initial state of the board and the general rules of the game using Boolean formulas. For example, the formula
states that if the value of the square A1 is \(k\), no other square in row A can have that value. If we combine all these constraints into a single expression, we obtain a single large Boolean formula of the \(9^3\) variables \(x_{ijk}\). Solving this formula means finding a subset of
variables that, when set to true, make the whole formula true.
The general problem of solving Boolean formulas is known as the satisfiability problem (SAT) and belongs to the famous class of NP-hard problems. Fortunately, many Boolean formulas that occur in practice (including those that describe Sudoku puzzles) are reasonably tame and can be solved efficiently using standard SAT solvers. An efficient Sudoku solver based on this
idea can be found at https://github.com/t-dillon/tdoku. Combinatorial algorithms in general, including backtracking and SAT solvers, are discussed in detail in volume 4B of The Art of
Computer Programming [62].