Answer required in python. Please answer all the parts of this question.

2.

Start Goal

1 4 3 1 2 3

7 8 __ 8 __ 4

6 2 5 7 6 5

a) Draw the search tree for solving this puzzle

b) Implement the Search Tree in Python (State clearly what Python structure you are to use).

c) Find the sequence of states to get from start to goal using:

i) Depth First Search

ii) Breadth First Search

iii) Devise a metric to improve the search using Hill Climbing

iv) Implement a beam search

d) Which search is most efficient?