The 8-puzzle, an instance of which is shown in the following figure, consists of a 3 x 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to reach a specified goal state (shown in the right of the figure) from a random initial state (e.g., the left of the figure) You will implement BFS, DFS, Greedy, and A* search algorithm using Python to solve an 8-puzzle problem Each algorithm's performance including completeness, optimality, time complexity, and space complexity need to be evaluated. As known, A* search is optimal and complete if the heuristic is both admissible and consistent1. In the class, two heuristics, h1 and h2, were introduced, where hi -the numbr of misplaced tiles and h2 - the sum of the distances of the tiles from their goal positions, also called the city block distance or Manhattan distance. 547 3 45 678 A typical instance of the 8-puzzle Both hi and h2 heuristics are admissible and consistent guaranteeing that an optimal solution can be found if it exists. However, the two heuristics are not equally efficient. In order to researching heuristics functions, you are asked to answer the following questions a) Compare the efficiency between hi and h2 in terms of how many moves to solve a demonstrated 8-puzzle problem b) The effective branching factor (b) is an estimate for the number of successor states generated by a typical node. What is the formula to obtain b? c) Run your program to crate a table containing number of generated nodes vs. depth for both methods i.e., A* using hi and A* using h2 d) Then use the above two pieces of information (formula and table) to create a list of effective branching factors vs. depth for the two methods e) Plot two figures for the above two tables f) (Bonus) Find a more effective heuristic function