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

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

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.