COSC$2007$O$24$W: Data Structures II

Assignment$-1$

Due$-$date: Friday, January $19,2024$ @$11$:$59$pm

Cut$-$off date: Sunday, January $21,2024$ @$11$:$59$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 $32$

fields. $31$ 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$2007$: 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

Submission Instructions:

Please note that the submitted work will be considered as your own work and you

confirm that you have not received any unauthorized assistance in preparing for or

doing this lab$/$assignment$/$examination$.$ You confirm knowing that a mark of $0$ may

be assigned for entire work.

Submit your complete Java source files $(.$java$).$ Comment your program carefully so that it can

be read and understood. If your program is not properly commented you may lose marks. See

marking scheme for details.

Marking Scheme:

You will receive full credits for the working code, otherwise zero. No partial credits!

Comments in the program: $5$

Complete program, no compile$/$logical error, and correct output: $45$