Solving Peg Solitaire using Backtracking

This post was originally published on my blog.

A few days ago I saw a post on Reddit where someone asked what an algorithm for solving Peg Solitaire might look like. If you read the comments, you'll notice that backtracking is the most common answer given. I really liked the idea and was curious to solve this puzzle. So in this post we'll solve Peg Solitaire with the help of backtracking.

There's also an example repository on GitHub.

But first things first. What is Peg Solitaire? Peg Solitaire is a single player board game where the player has to move pegs (pins) and remove them on a board in order to win. The rules are simple: each turn you can pick one peg, jump over a neighboring one (horizontal or vertical) and remove the one you just jumped over. The game is won when there's 1 peg left in the center of the board and it's lost when you cannot jump anymore or the last peg is not in the center. You're not allowed to jump over multiple pegs or multiple empty cells.

An example Peg Solitaire board (source)

Implementation

For the implementation we'll use Kotlin, but of course you can use any other language. Before we can implement the algorithm, we have to write some game logic first. Let's start with the board representation.

val board: Array<IntArray> = arrayOf(
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(1, 1, 1, 1, 1, 1, 1),
    intArrayOf(1, 1, 1, 0, 1, 1, 1),
    intArrayOf(1, 1, 1, 1, 1, 1, 1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
)

The board is encoded as matrix (2D array) including the following values:

• -1 => No cell (edge)
• 0 => Cell without pin (hole)
• 1 => Cell with pin

The printed board looks like this:

 ---------------
|     X X X     |
|     X X X     |
| X X X X X X X |          -1 => " "
| X X X o X X X |           0 => "o"
| X X X X X X X |           1 => "X"
|     X X X     |
|     X X X     |
 ---------------

How do we check if the player has won? As I just mentioned above, the game is won when the last pin is in the center of the board. The board center is at position board[3][3]. Quite simple:

fun hasWon(): Boolean = this.remainingPegs == 1 && board[3][3] == 1

Next, we create a class that represents a single move. It has two attributes: from and to. Both of them include a x and y coordinate that represents the position on our board. For example Move(Pair(2,3), Pair(2,5)) means that we want to move the pin at y=2|x=3 to y=2|x=5. The first value indicates the row (y) and the second one the column (x). In this case, the pin at y=2|x=4 gets removed. The method getPegToRemove() returns the position of the pin to remove.

class Move(val from: Pair<Int, Int>, val to: Pair<Int, Int>) {
    fun getPegToRemove(): Pair<Int, Int> = Pair((from.first + to.first) / 2, (from.second + to.second) / 2)

    override fun toString(): String {
        return "(${from.first}|${from.second}) => (${to.first}|${to.second})"
    }
}

Now that we have the representation of the game board and moves, we can write a method that returns us all possible moves for a given board position. Here, we again iterate over each cell with a pin and check for each direction (horizontal / vertical) if the direct adjacent cell is not empty (1) and that this one's neighbor is empty (0). Of course, we must take into account the edges of the game board.

fun getPossibleMoves(): List<Move> {
    val moves = mutableListOf<Move>()

    for ((rowIdx, row) in board.withIndex()) {
        for ((cellIdx, cell) in row.withIndex()) {
            if (cell != 1) continue

            val from = Pair(rowIdx, cellIdx)

            // Left => Right
            if (cellIdx <= 4 && row[cellIdx + 1] == 1 && row[cellIdx + 2] == 0)
                moves.add(Move(from, Pair(rowIdx, cellIdx + 2)))

            // Right => Left
            if (cellIdx >= 2 && row[cellIdx - 1] == 1 && row[cellIdx - 2] == 0)
                moves.add(Move(from, Pair(rowIdx, cellIdx - 2)))

            // Up => Down
            if (rowIdx <= 4 && board[rowIdx + 1][cellIdx] == 1 && board[rowIdx + 2][cellIdx] == 0)
                moves.add(Move(from, Pair(rowIdx + 2, cellIdx)))

            // Down => Up
            if (rowIdx >= 2 && board[rowIdx - 1][cellIdx] == 1 && board[rowIdx - 2][cellIdx] == 0)
                moves.add(Move(from, Pair(rowIdx - 2, cellIdx)))
        }
    }

    return moves
}

The next step is to implement a method for playing a given move:

fun move(move: Move): Solitaire {
    val newBoard = board.map { it.clone() }.toTypedArray()

    val toRemove = move.getPegToRemove()
    newBoard[move.from.first][move.from.second] = 0
    newBoard[toRemove.first][toRemove.second] = 0
    newBoard[move.to.first][move.to.second] = 1

    return Solitaire(newBoard, remainingPegs - 1)
}

This method accepts a Move and returns a new game instance including the new board and the number of remainingPegs - 1. Look how the board is updated using the from and to attributes of move. The variable toRemove contains the position of the pin we just jumped over and want to remove.

Last but not least the most important part: the backtracking algorithm. Here, we create a game tree using depth-first-search. Each node in our tree represents a board position. From the root node (starting position) on, we iterate over all possible moves and search recursively for the one that results in a win. If that move is found, we cancel the search, go back up the child nodes to the root node and return the move of each child node that lead to this winning move.

fun dfs(
    game: Solitaire = this,
): Pair<Move?, Boolean> {
    if (game.hasWon()) return Pair(null, true)

    // Read from memory
    val hash = game.board.contentDeepHashCode()
    if (memory.containsKey(hash))
        return memory[hash]!!

    val moves = game.getPossibleMoves()
    if (moves.isEmpty()) return Pair(null, false)

    // Play each move and call recursively. Pick first solution that was found.
    for (move in moves) {
        val newGame = game.move(move)
        val hasWon = dfs(newGame).second

        // Return move that lead to win & store in memory
        if (hasWon) {
            memory[hash] = Pair(move, true)
            return memory[hash]!!
        }
    }

    // Case when no solution was found.
    return Pair(moves[0], false)
}

The return value of this method is of type Pair<Move?, Boolean> containing the next move to play and a boolean whether the game is solvable or not. Moreover, when we have found a winning move, we'll store it in a memory to speed up subsequent searches in the game tree.

You should notice that the algorithm always returns the same solution. That's because we cancel the search as soon as the first solution was found. If you want to have more randomness, you have to continue the search at this point for more winning moves and pick a random one of them. You can also shuffle the list of possible moves. Watch out: both will make the algorithm much slower!

Performance

When simulating a complete game, you'll see that the algorithm solves the puzzle surprisingly fast. On my laptop (Huawei Matebook 14) a complete simulation runs in ~80ms. Without the memory it would take ~500ms, what is still very good.

var game = Solitaire()

val timeMS = measureTimeMillis {
    var counter = 0
    while (!game.hasWon()) {
        counter++
        val move: Pair<Move?, Boolean> = game.dfs()
        game = game.move(move.first!!)
    }
}

println("Done in $timeMS ms")

Nevertheless, you can still improve the performance by using symmetries for example. This article might be a help for you.

Check out the GitHub repo for an example usage and more code details.