Programming Assignment 1 - State-Space Search

Table of Contents

• Due Date
• Introduction
• The Assignment
  • Input
  • Output
  • Running the Solver

Due Date

This assignment is due on Thursday, 12 February, no later than 11:50 p.m.. See the turn-in page (last modified on 2015 February 7) for information about turning in your assignment.

Introduction

The peg puzzle (or tee puzzle or Cracker-Barrel puzzle) is a puzzle played on a equilateral triangular array of holes. The size of the peg puzzle is the number of holes on a triangle side (because the triangle is equilateral, all sides has the same number of holes). A peg puzzle of size n has n(n + 1)/2 holes.

The puzzle starts with some number of holes filled with pegs; traditionally all but one of the holes are filled with pegs. The puzzle objective is to remove one peg after another until only one peg is left on the board. A peg gets removed from the board when it's jumped by another peg. A peg can only jump another peg, it cannot jump an empty hole. A jumping peg must land in a hole, it cannot land on another peg. A jumped peg has to be removed from the board.

The puzzle ends when there are no more moves possible. The puzzle is solved if there's one peg left in a hole; if there's more than one peg left, the puzzle has not been solved.

The Assignment

Write a Java class that uses state-space search to solve an instance of the tee puzzle, or indicates that the puzzle instance has no solution. The solution should involve creating state-space representations for tee-puzzle instances, creating a state-space graph for the puzzle, and then searching the state-space graph for a solution.

Input

Input comes from the parameters of the solve() method defined in the TeePuzzle interface. Your Java solver class should implement the TeePuzzle interface. For more details, see the TeePuzzle interface TeePuzzle.java in the /export/home/class/mucs520/pa1 assignment directory.

Output

Running the Solver

$ java -cp /export/home/class/mucs520/pa1/pa1.jar:. main

in the directory containing your class files. The jar file can be found in the assignment directory /export/home/class/mucs520/pa1, or you may have a copy stashed elsewhere. If you do make a copy, make sure you keep it up-to-date with the copy in the assignment directory.