Question $2$

a$.$ Describe an admissible heuristic function and state two examples of heuristic functions you can

establish for an $8-$puzzle problem.

b$.$ Explain why problem formulation must follow goal formulation.

c$.$ In how many ways can you arrange $6$ different books on a shelf?

Question $3$

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 patterns. 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 blank is at a corner only two moves are possible

if it is at the centre all the four 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

Initial state

Goal state

Figure $1$: The $8-$puzzle

a$)$ Solve the $8-$puzzle using the Breadth$-$First Search algorithm, illustrating diagrammatically the

changes in states as you expand the nodes.

b$)$ Solve the $8-$puzzle using the Depth$-$First Search algorithm, illustrating diagrammatically the

changes in states as you expand the nodes.

c$)$ Solve the $8-$puzzle using the Greedy Best$-$First Search algorithm, illustrating diagrammatically

the changes in states as you expand the nodes.

d$)$ Solve the $8-$puzzle using the $A^{**}$ Search Algorithm, illustrating diagrammatically the changes

in states as you expand the nodes.

BONUS QUESTION $($This will make you get extra marks to add to the marks earned in the test$)$

A $97\%$ chance that two students will share the same birthday $($month and day$)$ should be achieved

by grouping how many students together.