An N-puzzle solver written for a class project.
python main.py <strategy> <parameter> <puzzle-file> <solution-file> <stats-file>where:
<strategy>— The algorithm that will be used to solve the puzzle. Can be one of the following:bfs(Breadth-first search),dfs(Depth-first search),astr(A*);<parameter>— The algorithm's parameter. In case of BFS and DFS, it is the search order specified by a string that is permutation of the following four upper case letters: L (left), R (right), U (up), and D (down). In case of A*, it is a heuristic that can be one of the following:hamm(Hamming distance), ormanh(Manhattan distance);<puzzle-file>— The path to the file containing the puzzle to solve. The format of this file is specified later in this document (see section Puzzle file);<solution-file>— The path to the file that the solution will be written to. The format of this file is specified later in this document (see section Solution file);<stats-file>— The path to the file that the additional information about the calculation process will be written to. The format of this file is specified later in this document (see section Stats file);
The program reads the initial state of the puzzle from a file in which the first line should contain two integers r and c separated by space that determine the vertical (number of rows) and horizontal (number of columns) dimensions of the puzzle, respectively. Each of the remaining r lines contains c space-separated integers that describe the location of the individual pieces of the puzzle, with a value of 0 indicating an empty space.
Example:
4 4
1 2 3 4
5 6 7 8
10 13 11 12
9 14 0 15
The program generates a solution file that contains two lines. The first line contains an integer n that specifies the length of the found solution (i.e., the length of the sequence of moves corresponding to the shifts of the free field that will lead the puzzle from the given initial state to the goal state). The second line contains a sequence of n upper case letters corresponding to the individual movements of the empty field within the found solution. If the program has not found a solution for the puzzle, then the solution file consists of only a single line, which contains the number -1.
Example:
7
LULDRRR
The program generates a file containing additional information about the calculation process. It consists of 5 lines, each of which contains a number representing respectively:
- 1st line (integer): the length of the solution found - with the same value as in the file with the solution (where the program did not find a solution, this value is -1);
- 2nd line (integer): number of states visited;
- 3rd line (integer): number of processed states;
- 4th line (integer): maximum recursion depth reached;
- 5th line (real number accurate to 3 decimal places): duration of the calculation process in milliseconds.
Example:
7
29
14
7
0.502
There is a benchmark.py script that can be used to measure the execution time of different parts of the program. Run it as follows:
python benchmark.pyThe task was to examine all the possible initial states of the 15-puzzle at distances 1-7 from the solved state (a total of 413 states). For the BFS and DFS strategies, all of the following search orders had to be used:
- right-down-up-left
- right-down-left-up
- down-right-up-left
- down-right-left-up
- left-up-down-right
- left-up-right-down
- up-left-down-right
- up-left-right-down
All the result were combined into a single CSV file (where space rather than comma was used as a separator). Next, the script plotter.py was used to generate bar diagrams showing the average solution length, average number of visited states, average number of processed states, and average recursion depth for each algorithm and parameter combination.
