Problem 1 (100%) Implement the LRTA* algorithms for solving the 8-puzzle. Your program should ask the user for the order of the 8 tiles and the space. Assume the tiles are numbered 1-8 and the space is number 0. Your program will then ask the user how many times the program should run from that start state. The program will then run LRTA* that many times for the given start state. The program will print out each move taken. If implemented correctly, your program should take fewer and fewer number of steps to find the goal state with each successive run.
Use the sum of the Manhattan distance of each misplaced tile as the heuristic function.
You will turn in a printout of your program (it should not be more than a couple of pages) as well as a sample run showing how it does better with each successive run. Make sure your code is well-commented. Make sure you sign the coversheet. The work is to be done solely by yourself.
