CSC$311-$ Introduction to Artificial Intelli...

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 depicts start state A$.$

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

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.

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

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.

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.

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.

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.

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 file OutputB.txt$.$

Follow the instructions below carefully:

You are required to program in Java and use object$-$oriented programming concepts. Save all your files in a compressed $(.$zip$)$ folder with the following naming convention

Call your Java program NineSoldiers. java

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

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.

An int value to store the $h$ value.

Write the necessary methods of the class including:

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

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

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

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 minPQ.

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 solut