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"):

  1. (make-node move f g h parent board) makes a new node data structure with the given values. The arguments are optional.
  2. (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)
  3. (make-priq) will make a priority queue that can be used for the open list: (setq open (make-priq))
  4. (priq-insert open new) insert the node new according to its f value.
  5. (priq-extract open) extract the node with the lowest f value.
  6. *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))