Problem $2$: DFS$,$ BFS$,$ IDS

$(13$ points$)$

Consider the following puzzle called "Moving Magic Square". It is played on a $33$ table containing each of the

numbers $1$ to $9.$ The number $9$ is the "movable number". You can move $9$ in four directions $($up$/$down$/$left$/$right$),$

and swap $9$ with the number in that direction. The initial state is shown in Table $1.$ As the player, we want

to move $9$ to reach a final state such that the sum of the three numbers on every row, column, and diagonal is

There are multiple states that satisfy this condition, and you can stop your answer when you find the first

satisfied state. $($Hint: You can define the operations in order of up$/$down$/$left$/$right$,$ which might be helpful for

fewer steps to reach the satisfied state.$)$

Table $1$: Initial state

A $(2$ points$)$: Formulate this as a search problem. What are the states, operators, initial state, and goal condi$-$

tion?

B $(2$ points$)$: Is this state space a graph or a tree?

C $(3$ points$)$: Draw the portion of the state space that would be generated by the Breadth$-$First Search $($BFS$)$

procedure and mark the order in which each state is expanded with the numbers $1,2,3...$ Do not create multiple

copies of states that are identical, and identify the states that are goal states.

D $(3$ points$)$: Draw the portion of the state space that would be generated by the Depth$-$First Search $($DFS$)$

procedure and mark the order in which each state is expanded with lower$-$case letters a$,$ b$,$ c$...$ Do not create

multiple copies of states that are identical, and identify the states that are goal states.

$E(3$ points$)$: Draw the portion of the state space that would be generated by the Iterative Deepening Search

$($IDS$)$ procedure and mark the order in which each state is expanded with upper$-$case letters A$,$ B$,$ C$...$ Do not

create multiple copies of states that are identical, and identify the states that are goal states.