USING THE INSTRUCTIONS FROM THE PICTURE BELOW $,$FIX THE CODE BELOW THE PICTURE AND ALSO SHOW RESULTS OF WHEN THE GOAL STATE IS REACHED.

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.$ CODE: import java.io$.*$;

import java.util.$*$;

class State implements Comparable $\{$

private int hValue;

private int$[]$ board;

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

this.hValue $=$ hValue;

this.board $=$ board;

$\}$

@Override

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

return Integer.compare$($this$.$hValue, o$.$hValue$)$;

$\}$

public int getHValue$()\{$

return hValue;

$\}$

List generateChildren$()\{$

List children $=$ new ArrayList;

for $($int i $=1$; i ; i$++)\{$

if $($board$[$i$]!=0)\{$

if $($board$[$i $-1]==0)\{$

int$[]$ newBoard $=$ Arrays.copyOf$($board$,$ board.length$)$;

newBoard$[$i $-1]=$ newBoard$[$i$]$;

newBoard$[$i$]=0$;

children.add$($new State$($newBoard$,$ calculateHeuristic$($newBoard$)))$;

$\}$

if $($board$[$i $+1]==0)\{$

int$[]$ newBoard $=$ Arrays.copyOf$($board$,$ board.length$)$;

newBoard$[$i $+1]=$ newBoard$[$i$]$;

newBoard$[$i$]=0$;

children.add$($new State$($newBoard$,$ calculateHeuristic$($newBoard$)))$;

$\}$

$\}$

$\}$

return children;

$\}$

private int calculateHeuristic$($int$[]$ board$)\{$

int displaced $=0$;

for $($int i $=1$; i ; i$++)\{$

if $($board$[$i$]!=$ i$)$

displaced$++$;

$\}$

return displaced;

$\}$

void printState$($FileWriter output$)$ throws IOException $\{$

output.write$("$

h $="+$ hValue $+"$

$")$;

for $($int i $=1$; i $$ board.length; i$++)\{$

output.write$($board$[$i$]+"")$;

$\}$

output.write$("$

$")$;

$\}$

$\}$

public class NineSoldiers $\{$

public static void main$($String$[]$ args$)\{$

try $\{$

File file $=$ new File$("$C:$\backslash \backslash$Users$\backslash \backslash$Vukosi$\backslash \backslash$IdeaProjects$\backslash \backslash$untitled$\backslash \backslash$src$\backslash \backslash$inputB$.$txt$")$;

Scanner sc $=$ new Scanner$($file$)$;

int$[]$ initialState $=$ new int$[14]$;

for $($int i $=1$; i ; i$++)\{$

initialState$[$i$]=$ sc$.$nextInt$()$;

$\}$

State startState $=$ new State$($initialState$,$ startStateHeuristic$($initialState$))$;

bestFirstSearch$($startState$)$;

sc$.$close$()$;

$\}$

catch $($FileNotFoundException e$)\{$

e$.$printStackTrace$()$;

$\}$

$\}$

private static void bestFirstSearch$($State startState$)\{$

PriorityQueue frontier $=$ new PriorityQueueComparator$.$comparingInt$($s $->$ s$.$getHValue$()))$;

frontier.add$($startState$)$;

Set explored $=$ new HashSet;

int moves $=0$;

try $\{$

FileWriter output $=$ new FileWriter$("$outputA$.$txt$")$;

while $(!$frontier.isEmpty$())\{$

State currentState $=$ frontier.poll$()$;

explored.add$($currentState$)$;

currentState.printState$($output$)$;

if $($currentState$.$getHValue$()==0)\{$

System.out.println$("$Goal state reached."$)$;

output.write$("$Goal state reached.

$")$;

output.write$("$Number of moves: $"+$ moves$)$;

output.close$()$;

return;

$\}$

for $($State child : currentState.generateChildren$())\{$

if $(!$explored.contains$($child$)$ && $!$frontier.contains$($child$))\{$

frontier.add$($child$)$;

$\}$

$\}$

if $($moves $>=700)\{$

$//$System$.$out.println$("$Maximum number of moves reached."$)$;

output.write$("$

Maximum number of moves reached.

$")$;

output.close$()$;

return;

$\}$

moves$++$;

$\}$

output.close$()$;

$\}$ catch $($IOException e$)\{$

e$.$printStackTrace$()$;

$\}$

$\}$

private static int startStateHeuristic$($int$[]$ board$)\{$

int displaced $=0$;

for $($int i $=1$; i ; i$++)\{$

if $($board$[$i$]!=$ i$)$ displaced$++$;

$\}$

return displaced;

$\}$

$\}$