CS 343: Heuristic Search: 8 Puzzle
Due: October 5, 2007.
Introduction
This assignment is to apply A* and IDA* search
algorithms to the 8-puzzle. The 8-puzzle is a small board
game for a single player; it consists of 8 square tiles numbered 1
through 8 and one blank space on a 3 x 3 board. (A
15-puzzle, using a 4 x 4 board, is commonly sold as a
child's puzzle. We will use an 8-puzzle to keep the search space
reasonable.) Moves of the puzzle are made by sliding an adjacent tile
into the position occupied by the blank space, which has the effect of
exchanging the positions of the tile and blank space. Only tiles that
are horizontally or vertically adjacent (not diagonally adjacent) may
be moved into the blank space.
Code for a representation for the state of an 8-puzzle and functions to
generate the legal moves and to apply an operator to a given state
are provided in the file /projects/cs343/8puz.lsp .
Implement A* and IDA* search algorithms and test them on the start
states and goal state shown below; in each case, measure and print out
the number of nodes examined and the number of moves to solve the
puzzle, as well as the sequence of moves.
*goal* *easy* *medium* *hard* *worst*
1 2 3 1 3 4 2 8 1 2 8 1 5 6 7
8 4 8 6 2 4 3 4 6 3 4 8
7 6 5 7 5 7 6 5 7 5 3 2 1
Heuristic functions h0 (zero), h1 (number of
tiles that are not in the right place), h2
(Manhattan distance), and h3 (Manhattan distance * 2)
are provided. Try each heuristic function with each problem.
How do the number of nodes examined and quality of solutions
compare? Note: if any search takes more than 2 minutes, just
stop it with control-C and assume that the algorithm was unable
to finish in reasonable time.
It is okay for you to adapt your A* and IDA* algorithms from the
last assignment for this one.
Data and functions are provided by loading the file
(load "/projects/cs343/8puz.lsp"):
- (make-node move f g h parent board) makes a new node
data structure
with the given values. The arguments are optional.
- (move node), (f node), (g node),
(h node), (parent node), and (board node)
are access
functions for the fields of a node. You can also use
these with setf to set values:
(setf (g node) 0)
- (make-priq) will make a priority queue that can be used
for the open list: (setq open (make-priq))
- (priq-insert open new) insert the node new
according to its f value.
- (priq-extract open) extract the node with the lowest
f value.
- *allops* is a list of all operators (moves).
(can-apply board op) tests whether an operator can be
applied to a given board.
(apply-op board op) applies the operator, making a
new board.
8-Puzzle Animation Program
Functions have been written that allow 8-puzzle boards
to be displayed graphically under XGCL Lisp. You may use these if you wish.
Just after starting XGCL (/p/bin/xgcl) and before loading your files,
enter: (load "/projects/cs343/8pdisp.lsp") .
The display function is: (display-solution start-board moves)
This function will display a solution one step at a time. moves
is a list of moves.
(display-solution *easy* (dfs *easy* 5))