The "Moving Magic Puzzle" is played on a $33$ grid with each cell containing one of the digits $1$ to

The digit $9$ is the "movable digit". It can be moved in four possible directions $($up$,$ down, left,

or right$),$ and swapped with the digit in that direction.

The goal is to arrange the digits such that sum of every row, every column and each of the two

diagonals sums up to $15.$ The are many possible configurations that can satisfy the goal, wo of

which are shown below:

Starting with the initial state shown below, answer each of the following:

$($a$)$ Formulate this as a Search Problem.

$($b$)$ Complete the Search Tree shown below, generated by the Breadth$-$First Search $($BFS$)$ for this

Notes:

i$.$ Use the graph version of the algorithm $($in which a node is explored only once$).$

ii$.$ Apply the actions is the order Up $($U$),$ Down $($D$),$ Left $($L$)$ and then Right $($R$).$

iii. Label the states as $($a$),($b$),$ etc. in the order they are visited by the BFS$,$ based on the

ordering specified in $($ii$)$ above.