CSE 472/572, Spring 2002

PROGRAMMING PROJECT #2

SOLVING 8-PUZZLES BY SEARCH

Last Update: 27 February 2002

Note: NEW material is highlighted

  1. Write a program (preferably in Lisp :-) 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:

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

    For more information on this heuristic, see the following documents in PDF format that I've put on the Web (also available in SEL):

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

    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. This does not have to be a formal, big-O-style analysis such as you would do in CSE 431/531 (although that would be nice!); an informal comparison will suffice for this project.

  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:

  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 For stylistic suggestions, see "Instructions for Word-Processed or Typed Papers".

  6. To help you in preparing your report, here are the things we'll be looking for:

    Following both the requirements for projects as stated in the syllabus and the requirements for this project, there are 3 major items of roughly equal importance:

    • the project description
    • annotated sample runs
    • documented code

    Here's the breakdown:

    project description:

    • description of project 2 (including an abstract!)
    • description of representation of 8-puzzle
    • analysis of efficiency of various search procedures
    (all 3 items above of roughly equal importance)

    optional: bug report (if your program doesn't work, you can recoup lost points by explaining your problems and how you might solve them with more time)

    annotated sample runs:

    • depth-first: run & annotation
    • breadth-first: run & annotation
    • uniform cost: run & annotation
    • best-first, h_a: run & annotation
    • best-first, h_b: run & annotation
    • best-first, h_c: run & annotation
    • A*, h_a: run & annotation
    • A*, h_b: run & annotation
    • A*, h_c: run & annotation
    (each of the above of roughly equal importance)

    documented code:

      IF you used your own, original code, THEN:

    • representation of 8-puzzle: code & documentation
    • depth-first: code & documentation
    • breadth-first: code & documentation
    • uniform cost: code & documentation
    • best-first: code & documentation
    • A*: code & documentation
    • h_b: code & documentation
    • h_b: code & documentation
    • h_c: code & documentation

      ELSIF if you used "borrowed" code, THEN:

      (a)

    • representation of 8-puzzle: citation for source & documentation
    • depth-first: citation for source & documentation
    • breadth-first: citation for source & documentation
    • uniform cost: citation for source & documentation
    • best-first: citation for source & documentation
    • A*: citation for source & documentation
    • h_a: citation for source & documentation
    • h_b: citation for source & documentation
    • h_c: citation for source & documentation
    (each of the above of roughly equal importance)

      (b) PLUS:

      variation (other search or 15-puzzle): code, documentation, run, & annotation

    (each of the above of roughly equal importance)

NEW
DUE AT START OF LECTURE, FRI, MAR 8
CODE TO BE SUBMITTED BY START OF LECTURE, FRI, MAR 8
NEW



Copyright © 2002 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 572/S02/proj2.27fb01.html