A computer can search for the answers to peg solitaire. Hint in the Peg Solitaire app, and the checking of answers on this site, use programs built on the same ideas. Here we introduce how they work in simple terms.
Trying Every Move in Turn
The most straightforward method is to repeat this: pick one available move and play it, then pick another available move and play it. When you hit a dead end, go back one move and pick another move you haven’t tried yet.
- From the current board, pick one available move and play it.
- If one peg is left, you’ve found an answer.
- If there are no moves left, go back one move and try a different one.
- When you’ve tried every move, go back one more move.
This method is called depth-first search. It’s the same thing a person does with “Undo,” repeated at an enormous speed.
Not Checking the Same Board Twice
In peg solitaire, playing in a different order often leads to the same board. On the English 33-hole board, there are more than 220,000 ways to play up to move 7, but only about 22,000 different boards result (How Many Solutions Are There?).
So the program remembers boards it has already checked and found to be dead ends, and when it meets one again, it turns back right away. That alone greatly cuts down how much it has to check.
With the program used on this site, an answer that starts the English 33-hole board from the center and ends in the center was found in an instant (in under 0.1 seconds). But it isn’t always fast. Searching the same way from a board where the second move was changed took about 9 seconds. The time it takes varies a lot depending on which move you try first.
Cutting Off Without Reading Ahead
Another trick is to stop searching as soon as you know that no way of playing from this board can reach the goal, without checking any further. This is called “pruning.”
The app prunes in the following two ways.
- Three-color coloring: If you color the board in three diagonal colors, each move flips the odd/even parity of the peg counts of all three colors. That means that from the current board, the holes where the last peg can end can be found by calculation alone (the three-color coloring article).
- The boss ball’s row and column: The boss ball moves two spaces at a time, so the odd/even parity of the row and column of its hole doesn’t change (Tips for Leaving the Boss Ball Last).
If the board has no hole at all that satisfies both conditions, there is no hole where the boss ball can end. Such a board is recognized as “unsolvable” without even reading ahead.
In the App’s Hint
Hint in the app searches for the next move that can reach the goal from the current board, and makes it glow with gold rings.
- Remembering the puzzle’s answer first: A “Puzzles” board is built by jumping backward, so the answer from when it was made is known (How We Make Puzzles That Can Always Be Solved). It remembers the boards along that answer path as “solvable,” so it can answer right away. Even for a board off the path, if the search joins the answer path along the way, it can stop there.
- Putting a limit on how much it checks: A single Hint checks at most 1.5 million boards or 3 seconds. On a big board, an answer may not come before then.
- Telling you how many moves to go back: When the current board can no longer reach the goal, or when it can’t tell within the limit, it examines the boards you can reach with “Undo” and tells you how many moves to go back, as in “Go back 3 to save it.” It examines those boards by halving the range repeatedly, so it finds the answer quickly even when there are many moves.
Hints for Solving It Yourself
The computer’s tricks can be used when a person solves it too.
- Remember dead-end shapes: A shape that failed once will fail again even if you reach it in a different order.
- Think from the goal: The holes where the last peg can end are decided from the start. If you decide on the hole you’re aiming for first, it’s easier to choose your moves (Leaving the Last Peg in the Center).
- Go back and try again: Like depth-first search, going back a little and trying a different move when you’re lost is the right way to do it.
