Peg Solitaire Game

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

Problem Description

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. 

Cross    Plus     Fireplace   Up-Arrow
Diamond    Pyramid  Solitaire "Cracker Barrel"

                  

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.

Programmer's Notes

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:

  1. In the previous version, it was possible to drag a hole in over a peg (and materialize a peg in the landing spot!).  Attempts to drag a hole are now ignored.
  2. For the triangular "Crackerbarrel" puzzle the size is set by the user when that puzzle type is selected.  To change the size it was necessary to select another type and then re-select Crackerbarrel.     There is now a "Change size" button visible for this puzzle type.
  3. Again for the Crackerbarrel,  during user play the program reported "No more moves available" when there were still valid diagonal moves left.  Now when the program says you're through, you really are!  

 Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

It would be user friendly to allow the user to "Undo" moves.
Plenty of room to experiment with alternative search sequences.  Top to bottom (or bottom to top) first, then left to right (or right to left),  Changing the order of the North South, East,  West direction checks will change the search pattern and thus the total moves to solution.  How about checking holes instead of pegs to find moves?    Is there some clue in the initial configuration  which would let us choose a search procedure to minimize the total search time?
Done March 2004  There is a triangular version of the game which  allows jumps in six directions.   The straightforward exhaustive search techniques used here may or may not work in the 6-way case depending on the size of the board.  
 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2013, Gary Darby    All rights reserved.