Write a program to implement the A$*$ algorithm in python that will solve the $8-$puzzle problem. The program will implement all three heuristics $($h$1,$ h$2,$ & h$3)$ from task $1.$ The program will also implement an additional heuristic, h$4=$ max$($h$1,$ h$2,$ h$3),$ and utilize it at each node. 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 values. Output metrics will be printed for all $4$ heuristics.

$(3)$ Try your program with the four configurations you described in task $1.$ Create a table that shows the metrics for all four configurations using the $4$ 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? Write the configuration. Why do you think solving this one takes a long time? You learnt 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?