CS 472/572, Spring 1997

PROGRAMMING PROJECT #2

SOLVING 8-PUZZLES BY SEARCH

Revised: 14 February 1997

1. Write a Lisp program that can use a variety of search methods to solve 8-puzzles. The program should take as input an initial state, a goal state (or goal-state test), a search method, and (if appropriate) a heuristic function. You should use at least the following search methods:

   • depth-first (or depth-limited),

   • breadth-first,

   • uniform cost,

   • best-first,

   • A*.

   For best-first and for A*, you should use the three different hs that we discussed in lecture, namely:

   • h_a(n) = W(n) = number of misplaced tiles in node n

   • h_b(n) = P(n) = sum of city-block (``Manhattan'') distances that each tile is from its goal-state location

   • h_c(n) = P(n) + 3*S(n), where S(n) = the sequence score =
     for all non-central tiles, if it is not followed by correct successor, score 2 else score 0, & if central tile is not blank, then it scores 1.

   For more information on this heuristic, see:

   • Nilsson, Nils J. (1971), Problem-Solving Methods in Artificial Intelligence (New York: McGraw-Hill): 65-68. (SEL Q335 .N52 1971; also on reserve at SEL)

   • Doran, J. E., & Michie, D. (1966), ``Experiments with the Graph Traverser Program'', Proceedings of the Royal Society of London, Series A. Mathematical and Physical Sciences 294: 235-259, esp. pp. 242-250. (SEL Q41 .L7(2); also on reserve at SEL)

2. For output, your program should be able to do at least the following 2 things:

   • In a ``problem-solving'' mode, it should print the sequence of states from the initial state to the goal state.

   • In a ``verbose'' (or ``debugging'' or ``analysis'') mode, it should output the entire search tree, with the chosen states highlighted in some way.

   Note that the output can be character-based; i.e., it need not use any fancy graphics.

3. For each search method and each heuristic function, analyze how efficiently it solves the problem.

4. You should (preferably) write your entire program from scratch. However, you may instead decide to use (or modify) off-the-shelf algorithms. If you do, then, first, you must acknowledge and cite the source of these algorithms, and, second, you must do one of the following variations:

   • Implement one or more other search methods (e.g., iterative deepening, bidirectional, IDA*, SMA*, hill-climbing, etc.) and analyze the performance of your program on them.

   • Extend your algorithm to 15-puzzles (i.e., which use a 4x4 array, rather than a 3x3 array).

5. As usual, your report should be in the form of a paper (e.g., a conference paper), with the annotated code and documented sample runs as an appendix, or embedded in the body of the paper, whichever seems more appropriate (a sample paper that you can use as a style guide is Shapiro, Stuart C. (1996), ``NimLearn: A Learning Nim Player''). For stylistic suggestions, see ``Instructions for Word-Processed or Typed Papers''.

DUE AT START OF LECTURE, TUESDAY, MARCH 4