N-puzzle solver for A* search, Hill-Climb, Simulated Annealing, Genetic Algorithm

You will be solving the N-Puzzle Problem using one of the following search strategies: 1. A* search 2. Hill-Climb 3. Simulated Annealing 4. Genetic Algorithm Your program should read input data through inputfile [login to view URL] and output to solution.txt. The input will look like this: 1 2 3 4 8 5 7 6 X More specifically, there will be a matrix of numbers separated by white space, with a new line to determine the end of a row. In one of the rows, there will be a single X, representing the empty space. The output for the above input should have this format: lurd 64 seconds Where each letter corresponds to the direction that the empty space is moved in sequential order from left to right to move to the goal state. Furthermore, l corresponds to left, u corresponds to up, r corresponds to right and d corresponds to down. If your program fails to produce a solution after 30 minutes, it will be aborted. If there is no solution to the puzzle, you should return an empty sequence.