Solves the sliding block puzzle using a best-first search algorithm.
Valid puzzles have dimensions n x m where both n and m are greater than 1.
The heuristic employed by the search can be either:
-
Manhattan (manhattan distance)
-
Total Distance (moves made so far plus manhattan distance)
Note that the latter makes the search equivalent to the A* search algorithm.
A puzzle is solved when its blocks are arranged in ascending order from left to right, top to bottom, like so:
<n> <m> <block(1)> <block(2)> ... <block(n*m-1)>
Blocks are placed into the puzzle from left to right, top to bottom.
3 3 5 1 4 3 7 2 8 6 0
To use the manhattan heuristic:
make manhattan < <input_file_path>
To use the total distance heuristic:
make total < <input_file_path>