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