## CS 343: Heuristic Search: 8 Puzzle

### 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.

```     (display-solution *easy* (dfs *easy* 5))