With Depth First Search
Garcia 6
Peg Solitaire
with Depth First Search
Iris Garcia
Larry Osborne
COSC 4135
21 April 2009
Peg Solitaire
Background
Peg Solitaire is a single-player board game that consists of pegs on a board of holes, and can come in many different shapes such as: cross, square, pyramid, triangle, diamonds, etc. The main purpose of the game is to eliminate all pegs on the board by jumping over pegs similarly to jumping pieces in the game of Checkers. As well as its different shapes, there is an unlimited amount of solutions for this game, but some may not be as optimal as others.
Design
The simplest peg solitaire design is the triangular peg board that is often referred to as the “Cracker Barrel” design. This design is formed like an equilateral triangle, where each edge has the same number of pegs. Similarly, each row has only one more peg than the row above it. To simplify implementation, this board can be represented as a tree in order to implement how to traverse it.
Depth First Search
Depth First Search is algorithm used to traverse a tree or a graph, and starts off at the root (or top node) and explores each branch of children in one direction. Once it reaches the end of a branch, it backtracks to the last available node in order to traverse the next branch. This may not be the most optimal solutions in solving Peg Solitaire problem, but it has proved to be one of the more effective solutions as cited by Gary Darby and Armando B. Matos.
Test Specifications
In order to test how optimal the Depth First Search Solution is in solving the Peg Solitaire problem, varying the size of the board can be useful in testing how fast it can be solved.
Files Included
§ Class Diagram.jpeg
§ Sequence Diagram.jpeg
§ Use Case Diagram.jpeg
Annotated Bibliography
Darby, Gary. "Peg Solitaire Game." DelphiForFun Home. 31 Mar. 2009 <http://www.delphiforfun.org/Programs/PegSolitaire.htm>. This source offers background information on several different techniques in solving Peg Solitaire. It also includes different representations of Peg Solitaire other than the "Cracker Barrel" design. It also implies that the Depth First Search as one of the most effective solutions.
Matos, Armando B. "Depth-first search solves Peg Solitaire." Computer and Information Science Papers CiteSeer Publications ResearchIndex. 31 Mar. 2009 <http://citeseer.ist.psu.edu/600260.html>. This article by Armando B. Matos goes into detail about using the Depth-First Search to solve the Peg Solitaire problem. Matos uses a tree to represent the pegs instead of a graph and gives computation type for implementing this algorithm with different representations of Peg Solitaire.
Muhammad, Rashid B. "Depth First Search (DFS)." Depth First Search (DFS). Kent State University. 31 Mar. 2009 <http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm>. This source explains the uses of depth-first search and details its algorithm.
Neller, Todd. "Uninformed Search." Gettysburg College Computer Science. Gettysburg College. 31 Mar. 2009 <http://cs.gettysburg.edu/~tneller/resources/ai-search/uninformed-java/index.html>. This source describes Peg Solitaire in a triangular hex grid, and gives a documented example of the source code.
O'Brien, Daniel M. "Peg Board Puzzle Solution Page." Daniel M. O'Brien - bootstrap page. 31 Mar. 2009 <http://www.danobrien.ws/PegBoard.html>. This source gives a more detail analysis of solutions for the "Cracker Barrel" or triangulated representation of Peg Solitaire.