PLEASE ANSWER EVERYTHING WITH ALL THE INFORMATION DO NOT PARTIALLY ANSWER THIS

In this you will investigate how different heuristics impact the performance of the A* algorithm. You will work on the 8-puzzle problem for this purpose. Complete the following tasks:

(1) In the class we learnt 2 admissible heuristics(Manhattan Distance (MD), Misplaced Tiles (MT)) for the 8-puzzle problem. Propose a 3rd admissible heuristic (Linear Conflict (LC) or anything else is fine). Give examples of 4 arbitrary initial state configurations of the puzzle. Do not use the examples from the lecture slides. Calculate the heuristic values for these four. Which one seems to be the most dominant among these four? Why? Provide an intuitive reasoning.

(2) Make a program to implement the A* algorithm in python that will solve the 8-puzzle problem. The program will implement all three heuristics from task 1. Your program will have two input options for the initial configuration. Either it can be taken as input from the user, or it can be randomly generated. The program will calculate three metrics to measure the performance of the program: time required, peak memory usage, and the number of nodes generated. Before starting to generate the nodes, the program will print the input configuration and its initial heuristic value. Outputs will be printed for all 3 heuristics.

(3) Try your program with the four configurations you described in task 1. Make a table that shows the metrics for all four configurations using the 3 proposed heuristics. Which heuristics gives the best performance for all four configurations. Why? Discuss using the concepts of dominance and time complexity.

(4) Try your program with some randomly generated configurations. Does it take a very long time (as if it never ends) for any of these configurations? Make the configuration. Why do you think solving this one takes a long time? You saw the theoretical time complexity of the A* algorithm in the class. Which component of this complexity do you think is causing the program to take such a long time? Why? What to submit: (1) The python program (.py file) from task 2. Add enough comments for readability. (2) A pdf document containing the solutions of tasks 1, 3, and 4.

PLEASE I BEG ANSWER ALL and provide code(python) and document ! please