In the $8-$puzzle of Figure $1,$ differently numbered tiles are fitted into $9$ spaces on a grid. One space is left blank so that the tiles can be moved around to form different pattems. The goal is to find a series of moves of the tiles into the blank space that places the board in a goal configuration. The following are legal moves, $($please note that if the blenk is at a comer only two moves are passible, if it is at the centre all the for moves are possible, if on the remaining spaces three moves are possible$)$:

Move the blank up$.$

Move the blank right

Move the blank down

Move the blank left

Goal state

Figure $1$: The $8-$puzzle

a$)$ Solve the $8-$puzzle using the Depth$-$First Search algorithm.

$[6]$

b$)$ Solve the $8-$puzze using the Breadth$-$First Search algonthm.

$[6]$

c$)$ Solve the $8-$puzzle using the $A^{**}$ Search algorithm.

$[6]$