Triangle Peg Solitaire

• Download source - 39.59 KB

Introduction

The 15-hole triangle peg board game is a modern version of a game that has been played in Europe since the end of the 17^th century. In the United States, Herbert M. Smith patented a triangular version of the game in 1891. It is also known as peg solitaire or the Cracker Barrel puzzle. The puzzle gained in popularity when the restaurant put one on every table to amuse patrons waiting for their food.

This program allows you play Solitaire puzzle also known as Peg Solitaire Puzzle. The game consists of 14 pegs set in a triangle shape with 15 holes like bowling pins, but with one more row. One of the spaces in the triangle is left empty, and the object is to jump pegs, removing each peg jumped, until you are left with only one. The program, in fact, implements a simple backtracking algorithm DFS to search for a solution starting from the current disposition of the pieces on the board.

Background

The main principle of this program is to demonstrate the concepts of recursive function, inherently recursive problem and backtracking. It also provides an object oriented vestment to backtracking, in the form of a reusable class holding all the backtracking logic.  In this assignment, you will write a program that solves a classic puzzle, sometimes called the triangle puzzle or peg solitaire. Solving this puzzle will require the use of a technique known as backtracking to search through all possible sequences of moves, which is easy to implement using recursion.

How It Works: A General Step

The Triangle Puzzle is a collection of 15 holes organized into a triangle, into which pegs are placed, leaving at least one empty hole. Typically, the puzzle begins with only one hole, as in configuration (a) below, where solid circles represent pegs, and empty circles represent holes. The object of the puzzle is to make a sequence of moves, each move causing one peg to be removed, such that only one peg remains. A Peg is removed only by "jumping" it with another peg. Hence, a legal move can only be made if there is a peg flanked by both another peg and a hole, arranged in a line. For example, configuration (b) shown below is obtained from configuration (a) by one jump, and then (c) is obtained from (b) by making a second jump.

Using the Code

I just want to give a real basic overview of the code. The source code in the project is very well commented, and should be easy to follow by adding some breakpoints on the mouse events.

This is the algorithm used in this peg solitaire solution.

DepthFirstSearch(Board b, Peg start)
{
      If (Grandchild.isEmpty())
            Jump();
            updateBoard(); //updates empty peg, location, etc.
      else
            backtrack();  // backtrack to previous and/or try right child
}

The main thing is the board, which is a ArrayList<T>. A BitArray manages a compact array of bit values, which are represented as Booleans, where true indicates that the bit is on (1) and false indicates the bit is off (0). For the game's purposes, true<code> represents that a peg is present and false<code> represents an empty hole. Below is the function InitializeBoard() that sets up a new game board:

Here is some code for presenting the game board. As you can see in the code:

public List<GameBoard> possibleBoards() {
            List<GameBoard> boards = new ArrayList<GameBoard>();

            for (int i = 0; i < 5; ++i)
                  for (int j = 0; j <= i; ++j) {
                        Position start = new Position(i,j);
                        List<Move> possibleMoves = Moves.getMoves(start);
                        for (Move move : possibleMoves) {
                              if (validMove(move))
                                    boards.add(jump(move));
                        }
			}
	return boards;
}

Game tree.java

 package play;
 import java.util.List;
 import java.util.ArrayList;
 import board.*;

  public class GameTree {
  GameTree level;
  GameBoard gb;
  List<GameTree> children = new ArrayList<GameTree>();

   public GameTree(GameBoard gb) {
            this.gb = gb;
      }

   public void addChild(GameTree child) {
            children.add(child);
      }

   public GameBoard getGameBoard() { return gb; }

   public boolean hasChildren() {
            return children.size() > 0;
      }

   public GameTree getFirstChild() {
            return children.get(0);
      }

   public void removeFirstChild() {
            children.remove(0);
      }

   public int numChildren() {
            return children.size();
      }
}

Move.java

This puzzle is getting solved by three steps. You start with the empty spot on the board jump and end as you can see in this code below.

package board;
public class Move {
      private Position start;
      private Position jump;
      private Position end;

      public Move(Position start, Position jump, Position end) {
            this.start = start;
            this.jump = jump;
            this.end = end;
      }

      public Position getStart() { return start; }
      public Position getJump() { return jump; }
      public Position getEnd() { return end; }

      public String toString() {
            StringBuffer sb = new StringBuffer();

            sb.append("{"+start);
            sb.append(","+jump);
            sb.append(","+end+ "}");
            return sb.toString();
      }
}

How the Program Works?

I used Depth First Search Algorithm (DFS) to create the game. I used NetBeans IDE 7.0. First, you can choose the location of the hole in the beginning. I have attached the program and output.

First time when I created the program, the place of the hole in the beginning of the program was fixed. Then I changed the program to input the place of the hole manually.

Conclusion

I had a lot of fun creating this game. I hope that this article helped you and that you will have a good time playing the game. Also, feel free to leave any feedback you might have. After creating this game of Artificial Intelligence, I have clear idea of the backtracking algorithm.

History

• 20^th October, 2011: Initial version