In eight_puzzle.py, write a function named process_file(filename, algorithm, param). It should take the following three inputs:

a string filename specifying the name of a text file in which each line is a digit string for an eight puzzle. For example, here is a sample file containing 10 digit strings, each of which represents an eight puzzle that can be solved in 10 moves:10_moves.txt

a string algorithm that specifies which state-space search algorithm should be used to solve the puzzles ('random', 'BFS', 'DFS', 'Greedy', or 'A*')

a third input param that allows you to specify a parameter for the searcher either a depth limit (for the uninformed search algorithms) or a choice of heuristic function (for the informed search algorithms).

Your function should open the file with the specified filename for reading, and it should use a loop to process the file one line at a time. We discussed line-by-line file processing earlier in the semester.

For each line of the file, the function should:

obtain the digit string on that line (stripping off the newline at the end of the line)

take the steps needed to solve the eight puzzle for that digit string using the algorithm and parameter specified by the second and third inputs to the function

report the number of moves in the solution, and the number of states tested during the search for a solution

In addition, the function should perform the cumulative computations needed to report the following summary statistics after processing the entire file:

number of puzzles solved

average number of moves in the solutions

average number of states tested

For example:

>>> process_file('10_moves.txt', 'BFS', -1) 125637084: 10 moves, 661 states tested 432601785: 10 moves, 1172 states tested 025318467: 10 moves, 534 states tested 134602785: 10 moves, 728 states tested 341762085: 10 moves, 578 states tested 125608437: 10 moves, 827 states tested 540132678: 10 moves, 822 states tested 174382650: 10 moves, 692 states tested 154328067: 10 moves, 801 states tested 245108367: 10 moves, 659 states tested solved 10 puzzles averages: 10.0 moves, 747.4 states tested 

(In this case, because BFS finds optimal solutions, every solution has the same number of moves, but for other algorithms this wont necessarily be the case.)

Notes/hints:

You can model your code for solving a given puzzle on the code that weve given you in the eight_puzzle driver function. In particular, you can emulate the way that this function:

creates Board and State objects for the initial state

calls the create_searcher helper function to create the necessary type of searcher object, and handles the possible return value of None from that function

Important: Make sure to create a new searcher object for each puzzle (i.e., for each line of the file). Otherwise, the searcher will still have information inside it from previous searches when it starts to solve a new puzzle.

When calling the searcher objects find_solution method, you should do so as follows:

soln = None try: soln = searcher.find_solution(s) except KeyboardInterrupt: print('search terminated, ', end='') 

Making the call to find_solution() in this way will allow you to terminate a search that goes on too long by using Ctrl-C. In such cases, soln will end up with a value of None (meaning that no solution was found), and you should make sure to properly handle such cases.

You should not use a timer in this function.

This function should not return a value.

Testing your function:

If you havent already done so, download the 10_moves.txtfile, putting it in the same folder as the rest of your files for the project.

Try to reproduce the results for BFS shown above.

Try applying Greedy Search to the same file. You may find that it takes Greedy a very long time to solve some of the puzzles, at least when using h1 (the num-misplaced-tiles heuristic). If this happens, use Ctrl-C as needed to terminate the problematic searches. When we processed 10_moves.txtusing our implementation of Greedy, we ended up using Ctrl-Cto terminate two of the searches:

>>> process_file('10_moves.txt', 'Greedy', h1) 125637084: 204 moves, 658 states tested 432601785: 12 moves, 13 states tested 025318467: search terminated, no solution 134602785: 78 moves, 221 states tested 341762085: 26 moves, 339 states tested 125608437: 162 moves, 560 states tested 540132678: 68 moves, 749 states tested 174382650: search terminated, no solution 154328067: 10 moves, 16 states tested 245108367: 48 moves, 49 states tested solved 8 puzzles averages: 76.0 moves, 325.625 states tested 

Its also possible for none of the puzzles to have a solution, and you should handle that situation appropriately. For example, this can happen if you impose a depth limit that is too small:

>>> process_file('10_moves.txt', 'DFS', 5) # depth limit of 5 125637084: no solution 432601785: no solution 025318467: no solution 134602785: no solution 341762085: no solution 125608437: no solution 540132678: no solution 174382650: no solution 154328067: no solution 245108367: no solution solved 0 puzzles 

Note that you cant compute any averages in this case, so you shouldnt print the averages line in the results.