Objective:$-$

The objective of this assignment is to use and implement recursion and backtracking algorithm.

Problem Statement:$-$

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$)$

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. The solution can be stored as a sequence of boards: one for each move. The board should be implemented as a Java class with an internal $7\backslash$times $7$ matrix $($two dimensional array$).$ In the backtracking algorithm you must compute all possible jumps for a given situation. Your program must include a class called Puzzle which includes the following methods:

$$ findSolution $($int move$)$: Backtracking algorithm to solve the puzzle. move $-$ current number of move, first move must be $1$

$$ main $()$: Starts the backtracking algorithm and prints out the solution as the sequence of all resulting intermediate board situation.

$$ print $()$: print current situation of the board.

$$ constructor : creates a new puzzle instance with empty solution and initial start position of all pegs.

$\frac{\frac{?}{?}}{x}=$ peg, $0=$ blank space, $-=$ illegal spaces where peg can't go

board $=$ new

$//$ Initialize the board with the provided configuration

this.board $=$ new char$[][]$

$\{\text{'}-\text{'},\text{'}-\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}-\text{'},\text{'}-\text{'}\},$

${\{}^{\text{'}}-{?}^{\text{'}},{?}^{\text{'}}-{?}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}-1,{?}^{\text{'}}-1\},$

${\{}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}}\},$

$\{\{$:${?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{O}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}}\},$

$\{\text{'}\{$:$x^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}},{?}^{\text{'}}{x}^{\text{'}}\},$

$\{\text{'}-\text{'},\text{'}-\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}-\text{'},\text{'}-\text{'}\},$

$\{\text{'}-\text{'},\text{'}-\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}$X$\text{'},\text{'}-\text{'},\text{'}-\text{'}\}$

$\}$;