Write a function to generate and store the tree. Students can define a data structure with various attributes such as,

Tree(1).ID, Tree(1).name, Tree(1).status, Tree(1).parent,

Tree(1).children, Tree(1) cost, Tree(1).state

Student must input the initial state of the 8-puzzle problem and then find the goal node from this initial node.

For example, following is the initial node, 4 5 8 1 7 3 2 6 And the final goal is 1 4 7 Nu00 3 6 You will make functions check_goal(state) and generate_children(state)

a) Apply greedy best search and A* search to find the goal. Use the heuristic function h1, number of misplaced tiles.

b) Apply greedy best search and A* search to find the goal. Use the heuristic function h2, a summation of city block distance of misplaced tiles from its original location. Time Space GBS with h1 A* with h1 GBS with h2 A* with h2 Submission:

Table (time complexity and space complexity) Working code Deadline: 20th of March 2021 Cheating of report or code is not allowed and zero marks will be awarded to the students who copy the code from each other.