Nine Little Soldiers is a puzzle in which $9$ numbered soldiers are trapped in a bomb shelter that has $13$ cells as shown in the figure below. A cell's number is shown either below or above the cell, and the soldiers are identified by the numbers inside a circle.

A soldier may only move into an adjacent empty cell and no more than one soldier may occupy a single cell. The puzzle requires you to move the soldiers so that soldier $(1)$ is in cell number $1,$ soldier $(2)$ in cell number $2,$ and so on up to soldier$(9)$ in cell number $9.$

The figure below denicts start state A$1.$

$1.$ Formulate the task as a search problem by defining the following: a state, the goal state and the moves $($actions$).$

$2.$Draw the first three levels of the state space with the initial state shown in the figure below $($start state B$)$ as the first level. Do not include repeating states.

$3.$Use the Displaced Soldiers heuristic: the number of soldiers that are not in their correct cells in any state. For example, the heuristic value of state $A$ is $1$ and of state $B$ is $9.$

Indicate the heuristic value for each state in your drawing for question $2.$ Show the values on the same drawing, i$.$e$.$ you do not need to

redraw the partial state space. $4.$ Write a Java implementation of the Best First Search algorithm for this problem.

a$.$ Your program must read the contents of a start state from a text file.

b$.$ The output of your program must show the sequence of nodes that are expanded. A

node in the graph can simply be displayed by printing the heuristic vale and showing

the contents of each cell from $1$ to $13$ in a single line. A zero entry represents an empty

cell. For example, State A can be displayed as:

h$=1$

$0234567891000$

and State B can be displayed as

h$=9$

$0000235689147$

c$.$ Your program must show the number of moves taken to reach the goal state.

d$.$ The output of parts a and b must be written to an output file an to the screen.

$5.$ Run the program first using state B as the start state and name the output file OutputB.txt$.$

Then run the program using state A as start state and name the output fCall your Java program NineSoldiers.java

$$ Write a class called State with the following variables to represent a state.

o An array with $14$ entries to represent the $13$ cells and the positions of the $9$ soldiers. The

array entry at index $0$ should not be used. This is so that a cell number correspond is the

same as its index in the array.

o An int value to store the h value.

Write the necessary methods of the class including:

o Accessor and mutator methods to retrieve and modify attributes of the class;

o Methods to perform moves $($i$.$e$.$ generate children states$)$

o A method to print the contents of a state.

$$ Use the $($built$-$in$)$ Java Collections PriorityQueue $($PQ$)$ data structure to store the frontier list of

expanded states. The PQ is of type State $($represented in the data structure described above$)$ and

is sorted in increasing order according to the heuristic value of each state. Two states that have

the same heuristic value may appear in any order in the PQ$.($Note that you have to overload

the comparison method in your PQ to sort the items in PQ in ascending order. Elements

are sorted according to their hValue and it is a min PQ$).$

$$ Test your Java program with both the two start states A and B shown above.

Show every state $($and its heuristic value$)$ that is expanded by the algorithm $($i$.$e$.$ removed from the

PQ$)$ as well as the final solution $($i$.$e$.$ goal state$)$ by printing it to an output $($text$)$ file $($called

OutputA.txt and OutputB.txt$,$ respectively$).$

Also print the states on the screen. So$,$ we want to see every move on the screen and in an output file.

Simply print the contents of array in one line followed by the heuristic value of the state.

Halt the execution of your program if it has not reached a goal state after $700$ moves.ile OutputB.txt$.$

Hint:

A partial outline of the class State is shown below. Add any necessary methods or parameters.

class State implements Comparable

$\{$

private int hValue;

private int$[]$ board $=$ new int$[14]$; $//$do not use entry $0$

public State$($int$[]$ board $)\{$

$...\}$

@Override

public int compareTo$($State o$)\{$

$...\}$

public int Get$\_$hValue$()\{$

$...\}$

$...$

$\}//$End of State class