COSC

$2$

$0$

$0$

$7$

O

$2$

$4$

W: Data Structures II

Assignment

$-$

$1$

Due

$-$

date: Friday, January

$1$

$9$

$,$

$2$

$0$

$2$

$4$

$$@

$1$

$1$

:

$5$

$9$

pm

Cut

$-$

off date: Sunday, January

$2$

$1$

$,$

$2$

$0$

$2$

$4$

$$@

$1$

$1$

:

$5$

$9$

pm

Objective:

The objective of this assignment is to implement and solve peg solitaire by using recursion and

backtracking algorithms.

Problem Specification:

The following game is actually a puzzle where the board has the form of a cross. It consists of

$3$

$2$

fields.

$3$

$1$

$$of these fields contain a peg. The single field in the middle of the board is empty. We

mark a peg with

$$

X

$$

$$and an empty field with

$$

O

$$

$$in the following examples.

X X X

X X X

X X X X X X X

X X X O X X X

X X X X X X X

X X X

X X X

The rules of this game are simple:

$$

$$you can take a peg and jump over another neighboring peg

$$

$$the peg you jumped over is removed from the board

$$

$$you solved the puzzle if at the end only on peg exists and is located in the middle of the board

At the start there are only a few possible moves, but the choices are increasing during the game.

Implement a recursive backtracking algorithm in Java, that finds a solution to this puzzle. Please

download the PegSolitaireSample before start. Your program must include a class called

PegSolitaireBoard which includes the following methods:

$1$

$.$

$$findSolution: Recursive and backtracking algorithm to compute all the possible moves move

$$

current number of move, first move must be

$1$

$2$

$.$

$$moveForward: Moves the

$$

X

$$

s and

$$

O

$$

s to the corresponding positions after the jump happens

$3$

$.$

$$moveBackward: moves the

$$

X

$$

s and

$$

O

$$

s back to their initial position before the jump occurred

COSC

$2$

$0$

$0$

$7$

: Assignment

$-$

$1$

$4$

$.$

$$checkMove: checks that the

$$

X

$$

$$performing the jump has one more

$$

X

$$

$$in between itself and

the

$$

O

$$

$5$

$.$

$$print: print the current state of the board