Implement regular iterative deepening and A* search for the 8-puzzle. The AIMA code library already has most of what you need for the 8-puzzle itself.
To get access to it, you need to add the following line to your .clisprc.lisp file in your home directory:
(aima-load 'search)From the AIMA documentation:
The representation of states is not the obvious one (a 3x3
array), but it is both efficient and fairly easy to manipulate. We
represent each tile
as an integer from 0 to 8 (0 for the blank). We also represent
each square as an integer from 0 to 8, arranged as follows:
0 1 2
3 4 5
6 7 8
Finally, we represent a state (i.e., a complete puzzle) as the
sum of the tile numbers times 9 to the power of the tile's square number.
For example:
1 2
3
1*9^0 + 2*9^1 + 3*9^2
8 . 4 is represented
by: + 8*9^3 + 0*9^4 + 4*9^5
7 6
5
+ 7*9^6 + 6*9^7 + 5*9^8 = 247893796
For your assignment, write two functions as follows:
(8-puzzle-itdeep state) - uses iterative deepening
(8-puzzle-a* state heuristic) - uses A* search with
appropriate heuristic
You should also implement the following two heuristic functions, either of which you can pass as arguments in 8-puzzle-solve2:
(num-wrong-tiles state) - counts the number of misplaced
tiles for the indicated state
(manhattan-distance state) - computes the Manhattan distance
for the misplaced tiles for the indicated state
Both functions should return a list containing (from to) pairs indicating where to move the blank square.
The goal state that you are trying to achieve is the following:
1 2 3
8 . 4
7 6 5
So for example, if the initial state was
1 . 2
8 4 3
7 6 5
The solution might appear as
((1 2) (2 5) (5 4))
Run some experiments with some random states. In comments at the end of search.lisp, describe your experiments and how iterative deepening, A* with the first heuristic, and A* with the second heuristic compare.
Here are various built-in functions you may find useful:
| (8-puzzle-print state) | displays the 8-puzzle associated with state |
| (move-blank state from to) | moves the blank from square from to square to |
| (blank-square state) | returns the number that the blank square is in |
| (neighbors square) | the squares that can be reached from a given square |
| (8-puzzle-location square) | return the (x y) location of a square number |
| (8-puzzle-state pos0 pos1 pos2 pos3 pos4 pos5 pos6 pos7 pos8) | define a new state with the tile number indicated in each position (use 0 for blank) |
| (8-puzzle-ref state square) | return the tile that occupies the given square |
| (abs n) | the absolute value of n |
Additionally, you'll need to randomly generate starting puzzles. Keep in mind that not all random puzzles are solveable. If you want to generate a puzzle that you know has a solution, write code to start with the goal state and iteratively randomly move the blank around. You then know that a solution is achievable in the number of steps your code ran, and possibly better.