9x9 Peg Solitaire

Last Modified August 24, 2005 Copyright © 2005 by George I. Bell

This web page documents some interesting properties and solutions for peg solitaire on the square 9x9 board.

Table of Contents:

• The Central Game: Inductive Technique, Shortest Solution, Symmetry
• Longest Finishing Sweeps

It is unfortunate that a standard chess board is just slightly too small to play 9x9 peg solitaire on. You can play the game on a go board, however the best board is really a computer. On a computer game you can easily backtrack and record move sequences, and taking the complement of a board position is trivial once a suitable button has been programmed. Many of the solutions below were discovered by hand using a Javascript program which I modified from a version by JC Meyrignac. Unfortunately this game is rather hacked up and I don't think anyone else would find it useful if they can't program in Javascript.

The Central Game

Shortest Solution

In 1962, Robin Merson found an elegant argument which gives a lower bound for the length of a solution on the 6x6 board. This argument can be generalized to any square (or even rectangular) null class board, but on an n x n board the bound is not very tight if n is odd. The complement problem from a corner must use at least (n/2+1)² moves, where when n is odd one must round n/2 down to the nearest integer. If the problem does not begin in a corner the bound is one less. On the 6x6 board this gives a lower bound of 15 for all problems that do not begin at a corner. In fact one can come up with solutions in 15 moves, so one immediately has a proof that they are optimal.

On the 9x9 board the lower bound indicates that any solution must have at least 24 moves. The best solution I have seen was constructed by Alain Maye, by hand, and has 34 moves (see below). It is likely it can be done in fewer than 34 moves, but I doubt the minimum length solution is under 28 moves.

Symmetry

The solution below answers this question. After 8 jumps (or 6 moves) the board position becomes square symmetric (shown in red). The next 60 jumps come in sets of 4 moves that are rotational copies of one another, so every 4 moves you pass through a position with rotational symmetry (shown in green). Then the final 11 jumps (or 6 moves) finish at the center. The final solution has 8+60+11=79 jumps (or 72 moves) and passes through 16 positions with rotational symmetry, 5 of them being square symmetric. It is not possible to go through more than 16 positions with rotational symmetry, because one cannot be reached in under 8 jumps from either end.

Longest Finishing Sweeps

The longest geometrically possible finishing sweep on the entire board has length 34, and ends at c1 (or any of the seven other symmetrically equivalent board locations). One of these sweep patterns is shown on the left diagram at the top of this page, but there are others. This pattern happens to be the only one that can actually occur in a single vacancy to single survivor problem, however.

From many places on the board it's possible to finish with a 32-loop. There are two essentially different 32-loop patterns possible on this board which have symmetry about both diagonals. These patterns are shown in the right three diagrams at the top of this page.

a1 b1 c1 d1 e1 f1 g1 h1 i1 a2 b2 c2 d2 e2 f2 g2 h2 i2 a3 b3 c3 d3 e3 f3 g3 h3 i3 a4 b4 c4 d4 e4 f4 g4 h4 i4 a5 b5 c5 d5 e5 f5 g5 h5 i5 a6 b6 c6 d6 e6 f6 g6 h6 i6 a7 b7 c7 d7 e7 f7 g7 h7 i7 a8 b8 c8 d8 e8 f8 g8 h8 i8 a9 b9 c9 d9 e9 f9 g9 h9 i9	33 26 34 26 33 26 34 26 33 26 20 27 21 26 21 27 20 26 34 27 33 26 32 26 33 27 34 26 21 26 20 25 20 26 21 26 33 26 32 25 32 25 32 26 33 26 21 26 20 25 20 26 21 26 34 27 33 26 32 26 33 27 34 26 20 27 21 26 21 27 20 26 33 26 34 26 33 26 34 26 33	32 24 32 24 32 24 32 24 32 24 20 24 20 24 20 24 20 26 32 24 32 24 32 24 32 24 32 24 20 24 20 24 20 24 20 24 32 24 32 24 32 24 32 24 32 24 20 24 20 24 20 24 20 24 32 24 32 24 32 24 32 24 32 24 20 24 20 24 20 24 20 26 32 24 32 24 32 24 32 24 32
Standard 9x9 Notation	Length of the longest sweep finishing at this location. Select links to see solutions.	Length of the longest loop finishing at this location. Select links to see solutions.
Color Legend: Green A solution exists to the complement problem. Red A solution exists from a single vacancy start. Blue No solution has been found but one may exist [link shows best solution found]. Yellow It has been proven that no solution exists [link shows best solution possible]. Note: The solution diagrams show how to play from the complement of the sweep positions to one peg. The solution ending with the long sweep can then be obtained by executing the jumps in exactly the reverse order, starting from a board position with one vacancy at the location of the finishing peg. In the diagrams, jumps that capture "white pegs" (see below) are colored in yellow.

We can prove it is not possible to play from any single vacancy start to any 32-loop beginning and ending at the center hole, e5. First, color the holes alternately as a chess board, with all the corners being black (above left figure). Each peg may be labeled as "white" or "black" and this label does not change during play because any jump begins and ends in the same color hole. The final sweep position consists entirely of white pegs, except for the peg that completes the sweep. During play to this sweep position, it is therefore critical to preserve white pegs. Notice that clearing a corner peg always requires jumping a white peg.

Second, we consider a parity count α around each corner. On the upper left-hand corner, this parity is the even or oddness of the number of pegs in the holes {b1, c1, a2, b2, a3}, as shown below.

α α     α α       α

The parity count α on the upper left corner

Notice that the parity α can only be changed by jumping a white peg, and clearing a corner does not change the parity α. We now make a careful accounting of the number of white pegs required and available.

If the initial vacancy is at the center, then all 4 parities α are initially odd, yet in the final sweep position they are all even. All 4 corners must also be cleared, requiring 4 more white pegs. The very first move must also jump a white peg, and it cannot be any of the moves mentioned previously. Therefore we need to capture at least 9 white pegs to reach the final sweep position, and there are only 8 available. It is therefore impossible to reach any 32-loop from the central vacancy start.

A similar argument show that no other starting location is possible either. If the initial vacancy is at b2, then the initial parity α around this corner is even, however it becomes odd after the first move. Hence we now require 8 white pegs to clear all the parities and corners yet we have only 7 (one being taken by the first move). If the initial vacancy is at e2, the first move does not jump a white peg, but there are only 7 available at the start, and 8 are needed. Finally, it can be shown that all 32-sweeps ending at e5 are in fact loops. So we have proved there is no 32-sweep ending at e5 reachable from a single vacancy start.

Can the same techniques be used to prove the 33-sweep and 32-loop ending at a5 are unsolvable? Probably. However, I have attempted to do this and it is considerably more complicated. Let me know if you can prove these unsolvable or find solutions to them.

Peg Solitaire Main Page ...