[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]Problem Description
Running/Exploring the Program
Peg Solitaire is another familiar game which is amenable to computerized solution. Here are seven common configurations which the program solves in a few seconds up to a minute or so.
The objective is to remove pegs by jumping them with another peg in any of the 4 major directions until a single peg remains in the center hole.
Background & Techniques
Although the theoretical number of board configurations is very large, in practice we can find solutions using a depth-first search in no more than a few million position tests. The best reference that I've been able to locate on the subject is a paper titled Depth-first search solves Peg Solitaire published in 1998 by Armando B. Matos. (A link in the top right corner of that page lets you download a PDF version of the paper.) (The site seems to be somewhat sporadic - if you want a copy of the paper and can't get to the site, send me a note) Among the surprising results Matos obtained, and I can confirm, is that the order of testing the nodes has a significant effect on the length of the search. For example, if moves are generated from left to right and top to bottom, the longest search is for the Up-Arrow configuration, which is solved after 17,998,001 positions are checked. If the order is changed to left to right and bottom to top, only 3,608 positions are checked before a solution is found!
George Bell has a very good page dedicated to the Peg Solitaire with his analysis of many kinds of solutions.
The Delphi version included here searches between 250,000 positions checked per second (on my 266 mhz laptop) and 750,000 per second on the new 800mhz Celeron. The longest search to find a solution requires about 13,000,000 position checks.
Non programmers are welcome to read on, or may want to skip to the bottom of the page to down the executable program.
A TBoard object holds an square array, B, of board positions of a TOccupied type field with values of Empty, Occupied or NotAvailable. A potential move is valid if 1) slot being checked is Occupied, 2) the adjacent hole in the direction being checked is Occupied and 3) the next position in the same direction is Empty. Because of this, a double row of unused (NotAvailable) array entries is defined all the way around the board (so the board is defined as 11 X 11 with only the middle 7 positions in each direction ever used . When we find a peg, we can always check two positions to the left, right , above and below with worrying about an "index out of range" exception. These dummy entries are frequently referred to a sentinels.
Moves is the central function which performs the search. It calls itself recursively after each move is made to find the next possible move. TBoard also contains a Path which holds the moves that got us to the current board position. When a valid move is found, we add it to Path, adjust the pegs array to reflect the move, decrement the peg count, and call Moves to check the next position. On entry to Moves, we check for a single peg in the center of the board and return true if found. If we examine all positions without finding a valid move, we return false. If we come back from a call to Moves with a false result, we undo the peg move we just made and keep searching.
The move record, TMove, is a dynamically allocated record with variables Frompoint and ToPoint. TMove was originally an object, but moves may be created and deleted millions of times in a run -- replacing the object form with a record reduced run times by 20% or so.
An OnStatus variable pointing to a procedure in the main form is set by the main form, Form1. As moves are tried the routine is called periodically, currently every 128,000 moves so that Form1 can update a progress display.
Aug 14, 2001 Addendum: Version 2 was posted today which allows users to drag pegs to make moves. From a users point of view, this makes it a playable game. From the programmer's viewpoint, the potential item of interest is the use of customized drag cursors. There's a new "Delphi-Topics" page about customizing cursors You can download the custom cursors used in Peg Solitaire from that page if you're interested.
I also modified the Solve routine to start from the current position, rather than the initial position. This allows user to click "Solve" part way through and let the program search from there. I've replaced PegGame1 with PegGame - no need to keep both versions around,
January 30, 2004 Addendum: Viewer Philippe sent a request for a specific solitaire board configuration not included in ,my original set. I ended up adding a "Custom board" selection that can be use to define arbitrary boards. Right clicking on any board will cycle the clicked cell through Unavailable, Empty and Occupied states. The default Custom board is Philippe's, which the program has not yet solved leaving a single peg. I added a "Solution Criteria" radio box to allow searches for "solutions" with 2, 3 or 4 pegs remaining .
March 4, 2004 Addendum: My old business partner asked recently if I could do a version of the triangular peg puzzle similar to those for in Cracker Barrel restaurants. I posted it today although I did not not redo all the drawing routines to present it as an equilateral triangle. So you can play a right angle triangle version with 5, 6, or 7 holes per side. (The Cracker Barrel version has 5 pegs per side. If you can solve these, just mentally rotate the puzzle by 45 degrees and Cracker Barrel will be labeling you as a "Genius". ) Note that "Auto-solve" has not yet solved the "one peg left" 7-per-side version so I do not know whether such a solution exits. If you let your PC run it long enough to find out, let me know. By the way, the same applies to a one peg solution for the default "Custom" puzzle.
January 10, 2007: Peg Solitaire has apparently made it to
cell phones these days. Viewer Bart wrote asking for help in solving the
game on his. It turns out that this is hardest solvable one I've seen so
far. I didn't find any shortcuts but Peg Solitaire Version 3 finds a
solution for one peg left in the center hole in about and hour after trying 4.3
billion moves! I added Bart's Board as one of the game
choices if you want to try your hand at it.
April 10, 2010: A viewer recently sent me two Peg Solitaire games which he says he purchased from a Target department store and which he was having trouble saving. The puzzles both specify that the final peg must land in a specific location (Column 4, Row 1 in a 7x7 array). My program handled custom puzzle generation but not specifying target cell for the last peg. Version 4.0 corrects that and also adds the ability to save and reload custom puzzles after I grew tired of re-entering them for each test. It turns out that one of the Target puzzles was missing a peg in it's definition and really was unsolvable. Three custom puzzle files are included with this download: Target1(Error).txt, Target1(Fixed).txt, and Target2.txt.
July 17, 2010: A sharp viewer found and fixed three bugs in Version 4.0, Version 4.1 implements his fixes pretty much intact:
Suggestions for Further Explorations
Copyright © 2000-2013, Gary Darby
All rights reserved.