1. Write Python programs to solve the 8-puzzle problem using (a) Iterative Deepening search up to one million nodes expanded, or when a goal node is reached. (b) A search using the two different heuristics mentioned in the book, i.e. number of misplaced tile, and sum of Manhattan distances. You should report the number of nodes expanded, the number of moves used in each search method and the paths found. Your program should get input from keyboard (or by input redirection) a list of 9 numbers, the first number will be the first tile in the first row, the second number the second tile in the first row, the fourth number the first tile in the second row . Input 0 for the empty tile