SE250:lab-X:rthu009

Task 1

The puzzle was a not 8 pice ie 9 pice including the space. So the number of states is 9! or 362880. The estimated number of edges i figured out with the following. This is because corners have 2 points then sides have 3 points and the middle has 4 points so therefore we have

(9! * 2.6666 ) / 2 = 483840

Task2

The algorithm is a best first search. It adds the states to a tree which is sorted using the Manhattan distance. The next state to examine is the minimum node of the tree which will be the state with the smallest Manhattan distance.