In Puzzles mode of the Peg Solitaire app, a board with a different shape is made each time you tap “New Game.” Yet every one of them can always be solved. This article explains how.

If You Build Them the Usual Way, You Can’t Tell If They’re Solvable

If you pick the hole shape and the peg placement at random, you end up with lots of boards that can’t be solved. To check whether a board can be solved, you have to look at every possible move, and that takes a long time when there are many pegs.

So the app uses a method that builds the puzzle backward from the answer.

Jumping Backward

One move in peg solitaire is: “a peg jumps over a neighboring peg into an empty hole, and the peg it jumped is removed.” If you do this in reverse, it becomes:

A peg goes back to the empty hole two spaces away, and one peg is placed in the empty hole in between

Each backward move adds one peg.

Starting from the Boss Ball Alone

You stack backward moves starting from a board with only the boss ball left (in other words, a board that has been cleared). Let’s look at a small example.

First, a board with only the boss ball.

Step 1: Move the boss ball back two spaces up, and place a peg in between.

Step 2: Move the peg you just placed back two spaces left, and place a peg in between.

Step 3: Move the boss ball back two spaces right, and place a peg in between.

That gives you a puzzle with 4 pegs.

The Backward Moves Are Exactly the Answer

If you play the moves you made in order from last to first, in the normal direction, you get the answer exactly. In the example above, if you make just the holes you used into the board’s holes and use that as the puzzle board, you solve it like this.

  1. Move 1 e1→c1
  2. Move 2 a2→c2
  3. Move 3 c1→c3
  4. After move 3 Pegs left: 1

The moves we built backward start from a cleared board, so if you follow them in the normal direction, only the boss ball is always left. That’s why every puzzle is guaranteed to have at least one answer.

What the App Adds

The app adds a few refinements to this method.

  • Reusing holes: When choosing a backward move, the app makes it easier to pick moves that reuse a hole that has already been used. The moves become tangled together, which makes it less likely that a puzzle is just a straight line of moves.
  • Tidying the board shape: For half of the boards it makes, it adds holes to make the shape left-right symmetrical. For the rest, it adds one or two empty holes at the edge of the board to change the shape. Even with empty holes added, the original answer can still be played as is, so it can still be solved.
  • The same puzzle from the same seed: Puzzles are made from a number called a “seed,” so the same seed and difficulty make the same puzzle on iPhone and on Android.

Checking Difficulty, and Rebuilding If It Doesn’t Fit

A puzzle built backward always has an answer. But that alone can make it too easy or too hard.

So the app checks each puzzle it makes by how many moves along the answer path make it impossible to save the boss ball once you play them (trap moves). It rebuilds the puzzle up to 24 times until the share of trap moves falls within the range for each of ★1 to ★5 (for the ranges, see the difficulty article).

Even for a ★5 Grandmaster puzzle (27 to 32 pegs), making one takes about 0.6 seconds on average on the Mac used for development. In addition, three puzzles are prepared in advance for each difficulty, and the app makes more in the background once they’re used, so players almost never have to wait.

There Isn’t Always Just One Answer

The moves built backward are just one answer. A board often has several other answers. The “boss ball practice” boards on the page about where to play were made with the same idea, and the 16-peg board has more than 3 million ways to solve it (How Many Solutions Are There?).

The app’s Hint remembers the answer from when the puzzle was made, so while you’re on the answer path it can tell you the next move right away. When you step off the path, a solution-finding program looks for another path (Solving It with a Computer).