Solving Peg Solitaire with Python

A Game for One

Peg solitaire is a board game for one player. [1] It is played on a board which has positions in a geometric arrangement. Each position can be either free or occupied. Usually the positions are marked by indentations that can be occupied by a peg or a marble.

Several board variants exist but I will focus in the 33-hole, English board. Emptying the entire board, except for one pin remaining in the center, is quite the challenge. A computer program can be used to find the moves that lead to that ideal, final position.

Peg solitaire has many peculiar properties, for example, the game can be played in reverse by exchanging the meaning of pegs and holes.

An Approach to Problem Solving

A method to solve this and other algorithmic problems can be found by dissecting the problem statement according to the following steps:

  1. Describe the initial state (pre-condition)
  2. Define the desired result (post-condition)
  3. Find the conditions that transformations of the initial state and the intermediate states shall satisfy, the game's rules. (invariants)
  4. Apply an algorithm that applies transformations until the desired state has been reached. That algorithm can be problem-specific, a (graph/tree) search algorithm …

The program presented in the following, that finds a solution for peg solitaire, fits this scheme but there are other problems that don't.

The Program

Initial Game State

The Board class holds a game state and defines the corresponding methods. The game state is kept as a list of lists of integers.

The __hash__ method generates a hash value that (uniquely) identifies a game state. This function will be used to keep track of the game states that have already been evaluated.

The clone method copies the game state of a Board instance into a new Board instance. A list comprehension is used to efficiently copy the 2-dimensional list of integers.

solving-peg-solitaire/solitaire.py (Source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
class Board(object):
    def __init__(self, board=None):
        # 0 = empty, 1 = occupied, 2 = invalid
        self.board = board or [
            [2, 2, 1, 1, 1, 2, 2],
            [2, 2, 1, 1, 1, 2, 2],
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 0, 1, 1, 1],
            [1, 1, 1, 1, 1, 1, 1],
            [2, 2, 1, 1, 1, 2, 2],
            [2, 2, 1, 1, 1, 2, 2],
        ]

    def __hash__(self):
        return hash(tuple([tuple(row) for row in self.board]))

    def clone(self):
        # Ca. 2x faster than copy.deepcopy()
        board_copy = [[peg for peg in row] for row in self.board]
        return Board(board_copy)

Scoring Games

The score method calculates the game score. The score is equal to the number of pegs remaining and a low score is better than a high score. The ideal solution has the last remaining peg in the center of the board. It's score is zero and therefore the ideal solution scores higher than any solution where the last peg is not at the center of the board.

solving-peg-solitaire/solitaire.py (Source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
    def score(self) -> int:
        # Count all pegs
        s = 0
        for peg in [p for row in self.board for p in row]:
            s += 1 if peg == 1 else 0

        # If there is only one peg left and it is in the center, the score is 0.
        if s == 1 and self.board[3][3] == 1:
            s = 0

        return s

Computing Possible Moves

All possible moves starting from the given game state have to be determined to exhaustively search for a solution. The method moves_for_peg finds the allowed moves for a peg at position (x, y). The possible_moves function calls the moves_for_peg method for all pegs on the board and assembles a list of possible moves. The format of the list is described in the listing.

solving-peg-solitaire/solitaire.py (Source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
    def possible_moves(self) -> List[Tuple[Tuple[int, int], Tuple[int, int]]]:
        moves = []  # Format: ((from x, from y), (to x, to y))

        # For each board position
        for x, row in enumerate(self.board):
            for y, peg in enumerate(row):
                # If occupied by a peg
                if peg == 1:
                    # Find valid moves for this peg
                    peg_moves = self.moves_for_peg(x, y)

                    moves.extend([((x, y), move) for move in peg_moves])

        return moves

    def moves_for_peg(self, x, y) -> List[Tuple[int, int]]:
        assert 0 <= x <= 6
        assert 0 <= y <= 6

        peg_moves = []

        # x, y offsets for moves towards top, bottom, left, and right
        move_offsets = [(-2, 0), (2, 0), (0, -2), (0, 2)]

        for (dx, dy) in move_offsets:
            new_x = x + dx
            new_y = y + dy

            # If new position is inside the board
            if 0 <= new_x <= 6 and 0 <= new_y <= 6:
                # If the new position is free
                if self.board[new_x][new_y] == 0:
                    # If there is a peg next to the current peg in the move's direction
                    if self.board[(x + new_x) // 2][(y + new_y) // 2] == 1:
                        peg_moves.append((new_x, new_y))

        return peg_moves

Altering the Game State

The move method changes the game state by executing a move. It also asserts a few conditions to ensure that the move is valid.

solving-peg-solitaire/solitaire.py (Source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
    def move(self, move: Tuple[Tuple[int, int], Tuple[int, int]]):
        (from_x, from_y), (to_x, to_y) = move

        # Delete peg from old position
        assert self.board[from_x][from_y] == 1
        self.board[from_x][from_y] = 0
        # Place peg at new position
        assert self.board[to_x][to_y] == 0
        self.board[to_x][to_y] = 1
        # Delete peg in between
        assert self.board[(from_x + to_x) // 2][(from_y + to_y) // 2] == 1
        self.board[(from_x + to_x) // 2][(from_y + to_y) // 2] = 0

        return self

Solving Recursively

A depth-first search is run recursively to find a solution to the puzzle. The solve_recursive function

  1. computes the boards hash value and tests the if the board has been played already. If yes, then the board position is skipped,
  2. retrieves all valid moves for the given state,
  3. test if there are no valid moves left - in that case the game is finished but only considered as solved if the score is equal to zero,
  4. calls itself for all game states that are the result of a valid move.

To later list the moves that lead to the solution, the move_memo variable keeps track of them.

solving-peg-solitaire/solitaire.py (Source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# Set of hashes of board positions. Used to skip boards that have been played already.
boards_played = set()

# Counters for statistical purposes.
statistics = {'Games finished': 0, 'Boards skipped': 0}


def solve_recursive(board, move_memo=()):
    if hash(board) in boards_played:
        statistics['Boards skipped'] += 1
        return
    boards_played.add(hash(board))

    moves = board.possible_moves()

    # If there are no moves left
    if len(moves) == 0:
        statistics['Games finished'] += 1

        # If the game is solved
        if board.score() == 0:
            return move_memo
    else:
        for move in moves:
            result = solve_recursive(board.clone().move(move), [mm for mm in move_memo] + [move])
            if result:
                return result

Running the Program

The solve_recursive function is called with a Board instance that holds the default, initial game state. The moves that lead to the ideal solution are then printed as a list of from/to-coordinates.

solving-peg-solitaire/solitaire.py (Source)

1
2
3
4
5
6
 
if __name__ == '__main__':
    moves_played = solve_recursive(Board())
    print(f"Finished {statistics['Games finished']} games! (skipped {statistics['Boards skipped']})")
    if moves_played:
        m = '\n'.join([f"{m[0][0]}, {m[0][1]} -> {m[1][0]}, {m[1][1]}" for m in moves_played])
        print(f"Solution found, moves:\n{m}")

The program typically completes after a few seconds with the solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
Finished 1063 games! (skipped 19940)
Solution found, moves:
1, 3 -> 3, 3
2, 1 -> 2, 3
0, 2 -> 2, 2
0, 4 -> 0, 2
2, 3 -> 2, 1
2, 0 -> 2, 2
2, 4 -> 0, 4
2, 6 -> 2, 4
3, 2 -> 1, 2
0, 2 -> 2, 2
3, 0 -> 3, 2
3, 2 -> 1, 2
3, 4 -> 1, 4
0, 4 -> 2, 4
3, 6 -> 3, 4
3, 4 -> 1, 4
5, 2 -> 3, 2
4, 0 -> 4, 2
4, 2 -> 2, 2
1, 2 -> 3, 2
3, 2 -> 3, 4
4, 4 -> 2, 4
1, 4 -> 3, 4
4, 6 -> 4, 4
4, 3 -> 4, 5
6, 4 -> 4, 4
3, 4 -> 5, 4
6, 2 -> 6, 4
6, 4 -> 4, 4
4, 5 -> 4, 3
5, 3 -> 3, 3

References & Further Reading

[1] https://en.wikipedia.org/wiki/Peg_solitaire

Pólya, George, and John H. Conway. How to Solve It: a New Aspect of Mathematical Method. Princeton University Press, 2014.