Software Design Specification for a Triangular Peg Board Game
By Leo Gonzalez
1.0 Introduction
This document describes the design of a single player interactive triangular peg board game with a variable number of pegs. The board is an equilateral triangle, with rows 1 through n, where row i has i holes. The rows are offset, so each 2 adjacent holes form an equilateral triangle with the hole in the row above it. The starting position has a peg in each hole except for the topmost hole. A legal move consists of a peg jumping horizontally or diagonally over an adjacent peg and into an empty hole. The peg that is jumped is removed from the board. A peg cannot jump over a hole. The player wins if there is only one peg remaining on the board. If no legal move is possible and there is more than one peg on the board, the player loses.
2.0 System Overview
This program uses an object oriented design using C++.
3.0 Design Considerations
General Constraints
The program will be launched from the command line. The display will consist of text and the player will type commands to allow the software to run on a wide variety of hardware.
Goals and Guidelines
This design tries to improve efficiency by minimizing the number of game states that are searched when the player directs the program to find a solution.
4.0 System Architecture
The algorithm of the main program can be summarized in the following pseudocode that is repeated until the user exits the program.
Prompt user for command
If command is valid, execute
Else Notify that command is not valid
The possible commands are shown in figure 1.
User Interface
The display will use text to simulate a peg board. This is a 3 level board.
0,0:0
0,1:1 1,1:1
0,2:1 1,2:1 2,2:1
The coordinate system is based on George Bell’s Skew Cartesian coordinates system. The player will move by entering in the To and From coordinates. For example 2,2 0,0 would jump the peg located at 2,2, to 0,0 with the resulting board of
0,0:1
0,1:1 1,1:0
0,2:1 1,2:1 2,2:0
Internal Representation of the Board
The program defines a PegBoard Class and a MoveList Class. The PegBoard Class uses the MoveList class to represent both the moves made by the player. When the player commands the program to solve, the PegBoard creates lists of legal unique moves to be searched. These classes are shown in Figure 2. The interaction between the Player and the classes is shown in Figure 3. The PegBoard class uses a two dimensional array to represent the current board state. The MoveList class uses a pair of two dimensional arrays to represent the From and Two coordinates.
5.0 Policies and Tactics
The program will use a depth first search algorithm with backtracking to find a game state that is reachable from the current state in which there is only one peg left. If there is no such game state, the player will be notified that there is no possible solution from the current board configuration. The player will always have the option to undo moves and try to find a solution from a previous state. Because every move removes exactly one peg from play, every possible solution will have exactly n-1 moves, where n is the number of pegs. Therefore, any solution found will have the minimum number of moves. When searching for a solution, the program will identify pegs that will lead to identical game states as other pegs, and removing them from consideration as possible moves. This solution is more efficient than a brute force approach. The recursive algorithm for finding a solution is as follows
Create a possibleMoves list
Check current board for symmetry
Add unique pegs to possibleMoves list
For each possible move in the list
execute move
if one peg left, return solution.
Else solve current board.
Backtrack
If it backtracks to the top level, and there are no possible moves left, no solution was found.
6.0 Testing
The program should be tested with different sequences of commands as the player has the option to enter any command at any time. Solutions that are found by the program should be tested by hand to confirm their accuracy. Multiple levels of board should also be tested.
Bibliography
“Solitaire Puzzle with Backtracking”, by Paolo Martinoli
http://www.codeproject.com/KB/cpp/SolitairePuzzle.aspx
“Triangular peg Solitaire”, by George Bell
http://www.geocities.com/gibell.geo/pegsolitaire/tindex.html#gpjr
“Solving Triangular Peg Solitaire” by George I. Bell. Journal of Integer Sequences, Vol. 11(2008), Article 08.4.8
http://arxiv.org/PS_cache/math/pdf/0703/0703865v6.pdf