CSE 150 Programming Assignment #1

Date assigned: April 7, 2007

Date due: 11:59:59 April 22, 2007

 

In this programming assignment, you will be solving a more general form of the 8-puzzle. Rather than be limited to strictly 3x3 puzzle, your solver should take any size puzzle. The puzzle can be described as an m x n array of digits 1 through (mxn - 1) with one empty square, marked with a 0. Initially, the puzzle will be arranged randomly (or rather, as the result of a series of random moves to ensure that it's solvable). The goal is to have the digits arranged in order (left to right, top to bottom), with the empty square located in the upper left corner.

 

Tiles can be moved into the empty space. The best way to represent this computationally, however, is to move the empty space. The empty space can move up, down, left, or right, but may not be moved off the board.

 

See R&N pages 64-65 for an alternative description of a 3x3 puzzle.

 

Logistics:

You can work alone or in groups of at most 3. Code must be submitted (with comments) by the due date. Use of Java for this assignment is encouraged - if you'd rather use something else, please discuss it with the TA. A copy of your write up as a pdf should be included. Turn in the code using the turnin script. More specifically: tar up your files, then type 'turnin -c cs150s ' where is the name of your tarfile (the -c cs150 s can be omitted if you've run prep, but better safe than sorry). Files are timestamped, so make SURE you submit before the deadline. Note that only your most recently turned in file is saved.

 

Since the original due date was April 18, ten points of extra credit will be given for projects submitted by that time.

 

Hard copies of write-ups are due at the beginning of class the following class (4/24), printed and stapled. Code should be included in the printout. Write-ups should include a brief description of the approach taken, answers to any questions posed, and sample output on some examples. See below for more details on the content of the write up.

 

Half of the points are based on the quality of the write-up and the comments. The other half are based on the performance of your code, both as reported in your write up and on a test set of problems. Bonus points may be awarded at the TA's discretion for going above and beyond the HW's description.

 

Points will be deducted for not following these instructions. Note that no late programming assignments will be accepted!

 

Assignment

  1. Write a puzzle class. Your puzzle should:
    1. Be able to generate random puzzles. Remember to start from a solution and move tiles; otherwise your puzzle may not be solvable. It should be able to generate puzzles of any size (nxm). You probably want to give it an argument saying how many random moves should be used.
    2. Read in puzzles from text files. This will be important to run the test set. Files will be in the form of comma separated values, with each line marking a row in the puzzle. Sample files are included below.
    3. Provide a good interface for the valid moving of tiles.
    4. Determine when the board has been solved.

 

  1. Write a depth first solver. This should be able to be run from the command line. For example, in Java to load the puzzle in samplePuzzle.txt and have a depth limit of 100 this should be run via "java DepthSolver.class samplePuzzle.txt". (This depth limit was meant to only apply to the depth first solver, but it shouldn't matter.) Your program should take as an additional argument an alternate max depth, as in "java DepthSolver.class samplePuzzle.txt 10". Your program should display to the screen the following information once a puzzle is solved (or all possible sequences of moves up to the depth limit have been tried without success):
    1. How many moves to reach a solution?
    2. How large did your queue get?
    3. How many states did you visit?

 

  1. As with (2), but for a breadth first solver. Call it BreadthSolver.

 

  1. As with (2), but for an iterative deepening depth first solver. Call it IDSolver.

 

  1. As with (2), but for A* with Manhattan distance as a heuristic. Call it AstarSolver.

 

  1. Extra credit: As with (2), but using IDA* with Manhattan distance or other distances as a heuristic. Call it IDAStarSolver.

 

Write up:

Please describe the approach taken. What kind of testing did you do, and how did your methods fare? Did all your search methods succeed in finding a solution? If not, what could you do to remedy that (or what did you do to remedy it)?  For part (5), did you try any other heuristics? (Hint: more credit for these!)

 

Also, perform some analysis on the efficacy of the different approaches with different puzzles. Two possible ways to vary the complexity of a puzzle is in its size or the number of random moves used to generate the puzzle. Your write up should include at least one graph.

 

Testing:

Your programs will be run on several puzzles. Test set files will be in the form of comma separated values, with each line marking a row in the puzzle. Parts 2-5 should be able to be called from the command prompt with a file name given. Your own reported testing should be thorough enough that there are no surprises here.

 

Here are two examples of the format. Additional sample files may be added at a later date.

easy2x2.txt

easy3x2.txt

 

Hints:

-Start testing on small, trivial problems (such as the above examples).

-Try to optimize code-reusability. Once parts 1&2 have been coded, parts 3-5 should be trivial. Keep in mind that you may be able to use some of this code in future assignments if your classes are set up properly.

-You may want to introduce additional command line arguments for your testing. Be sure to document this.