1. Write a program to solve the 8-puzzle problem using the uninformed searching techniques breadth-first search (BFS) and iterative deepening search (IDS). The input to your program are the numbers 0, 1, ..., 8, specifying the tiles number in the top-left, top-middle, ..., bottom-right positions respectively, in which 0 represents the blank. The output of your program is the sequence of moves that

2. Write a program to solve the 15 puzzle problem using A* searching technique, in which Manhattan distance (or something better, if you can come up of your own) is used for the h-value of a state. The input to your program are the numbers 0, 1, ..., 15, specifying the tile numbers so that the first 4 numbers represent the tiles in the first row, the next 4 numbers represent tiles in the second row, etc., in which 0 represents the blank. The output of your program is the sequence of moves that lead to the following configuration