CS 61B Project 3

A solution to this assignment is due by 11:59pm on Monday, May 7. You may work in a partnership of two students. Submit one solution per partnership, and include both your names in all files you submit. Your solution directory, named proj3, will include all the .java files relating to your solution plus a file named README whose contents are described below. Detailed design, and the coding and testing of your solution to this assignment should be your own work or that of your partner.

Background

Those of you who spend much time in toy stores may be familiar with "sliding-block" puzzles. They consist of a number of rectangular blocks in a tray; the problem is to slide the pieces without lifting any out of the tray, until achieving a certain configuration. An example (from Winning Ways, E.R. Berlekamp et al., Academic Press, 1982) is shown in Figure 1.

    sliding block puzzle 1

"Virtual" versions of these puzzles are available on the Web, for example, here.

Problem

Write a program named Solver.java that produces a solution to a sliding-block puzzle (if a solution exists) in as little execution time as possible. Your program need not produce the shortest possible sequence of moves. Input to your program will come from the command line and from files named there:

Thus your program would be run with the UNIX command

    java Solver [-oinfo] initialConfigFile goalConfigFile

where the -o argument is optional, info is the debugging information you supply, and initialConfigFile and goalConfigFile name the files containing the initial block configuration and the goal configuration respectively. You may also supply these arguments to Eclipse.

A solution to the puzzle will represent a sequence of position changes of blocks that, when starting with the specified initial configuration, ends up with blocks in the positions specified in the goal. The only legal moves are those that slide a block horizontally or vertically—not both—into adjacent empty space. Blocks may only be moved an integer number of spaces, and either the row or the column will be the same in the start position as in the end position for each move. (It's not legal to rotate the tray of blocks.)

Your program should produce a line of output for each block move that leads directly to a solution. Each such line will contain four integers: the starting row and column of the upper left corner of the moving block, followed by the upper left corner's updated coordinates. Example output appears below; the indicated moves, applied to the starting configuration of Figure 1, achieve the goal in Figure 2. (The annotations would not appear in the solution output.)

     1 1 0 1   move the 2x2 block up
3 1 2 1move the 1x2 block up
4 1 3 1move a 1x1 block up
4 2 3 2move another 1x1 block up
4 0 4 2move the leftmost 1x1 block two spaces over

If your program, run with debugging output disabled, finds a solution to the puzzle, it should exit normally after producing only output as just described, that is, the lines representing block moves that solve the puzzle. In particular, if the initial configuration satisfies the goal, your program should exit normally after producing no output. If your program cannot find a solution to the puzzle, it should exit with the call

	System.exit(1);

again after producing no output.

You should check that command-line arguments are correctly specified, but you may assume that the initial and goal configuration files are free of errors. You may also assume that the length and width of a tray are no larger than 256.

Time/space tradeoffs

Basically, your program will search the tree of possible move sequences to find a solution to the puzzle. It will implement several operations; questions you are to consider in your program design include those outlined below.

Some of these questions can be answered with careful analysis. Others require empirical evidence. Incorporate in your program sufficient output information (governed by debugging options—see below) to provide this evidence. Discuss your answers to all these questions in your README file (see below).

Miscellaneous requirements

The amount of space your program needs is not an important consideration, except that your program has to fit in the default allocation of memory provided on the workstations in 275 Soda. An experiment we recommend is to determine how many configurations you can add to a hash table before you run out of memory. (The blocks in the puzzle described in Figure 1 may be moved into 65880 different configurations. The blocks in the diagram below may be moved into 109260 different configurations.)
    sliding block puzzle 2

You should associate debugging output with program events appropriately, and choose an appropriate debugging level for each set of output. Your debugging output facility should allow the user to select both the classes for which output is produced and the level of detail of output. Any interesting event that happens in your program—e.g. making/unmaking a move, encountering a previously seen configuration, determining the set of possible moves, or comparing a configuration with the goal—should be displayed by debugging output at some level. You should also incorporate output that will help you make implementation decisions about time/memory tradeoffs. Describe your debugging output facility in your README file (see below).

You are to include a isOK method with each nontrivial class. When a class's debugging option is enabled, a call to isOK should accompany each change to objects in the class. The isOK method should throw IllegalStateException with an informative message if it finds a problem.

You are also to provide black-box tester classes and glass-box main testing methods for your nontrivial classes.

Organize your program into classes that allow easy substitution of efficient code for inefficient code or of one algorithm for another (e.g. depth-first move processing for breadth-first) in each area. Use straightforward algorithms where possible. Your methods should not be overly long, complex, or repetitive. All data fields and methods within each class must have the proper public/private/protected/package qualifier. In particular, you are not allowed to make things public that would let a user corrupt your data structures (even if none of your own code would do this).

Your code should display good documentation and style. Provide an overview comment with each class that describes the abstract object and any invariants on the abstract object state (e.g. "A Counter represents a mutable, non-negative, non-decreasing integer counter."). Accompany each method with descriptions of its preconditions and effects or return value. When throwing exceptions, supply informative messages. Give your variables and methods informative names that conform to conventions used earlier this semester (class names capitalized, names of constants in all upper case, and names of data members uncapitalized). Indent your code appropriately.

The README file

A substantial part of the credit for this project comes from the README submitted in your proj3 directory. This file should include the information listed below, answering all the questions in each category.

In general, comments in your code will describe information specific to the corresponding class, while the README file contains information that relates classes and describes and provides rationale for design and implementation decisions. However, your README file should be written to be read on its own without a copy of the program code at hand, so there may be some information duplicated in writeup and code.

We encourage you to build the README file as you design, code, and test rather than putting it off until the end.

How your program will be graded

This project will earn up to 120 points, allocated 80 for the program and 40 for the writeup. These points will be scaled to half your project grade (18% of your total grade). Grading will proceed as follows.

  1. Your writeup will be examined for information about your tray data structure, and your isOK methods for the tray and blocks will be evaluated.
  2. Your program will be compiled using the command
    	javac -O Solver.java
    
    If it fails to compile, you get no more program points. The "-O" (minus-Oh) option turns on optimization, and should be used for production runs. For debugging, use Eclipse.
  3. Your program will be run, using the command
    	java Solver initialConfigFile goalConfigFile
    
    on a selection of simple puzzles. (These puzzles are online in the directory ~cs61b/code/proj3/easy.) You must correctly solve almost all of these puzzles, using under two minutes of execution time for each puzzle, to earn more than 50 program points. (You are of course not allowed to "hard-code" solutions to these puzzles into your program.)
  4. Your program will then be run, again using the command
    	java Solver initialConfigFile goalConfigFile
    
    on a selection of difficult puzzles (online in the directory ~cs61b/code/proj3/hard), using a lightly loaded EECS workstation configured the same as the Sun Ultra-20 workstations in 275 Soda. (The "clients" command will tell you which workstations these are.) Each one you solve in under two minutes of execution time earns you more points, up to a maximum of 80. Note that we will not be supplying arguments to the Java interpreter that modify the default memory allocation or the default maximum size of the system stack.
  5. Stylistic and organizational attributes of your program will then be evaluated to complete your program score. These include information supplied in comments and variable names, formatting and use of white space, organization, a correct isOK method for each class, and appropriateness of debugging output. We will assign a percentage score to these aspects of your code; 100% means no flaws, 90% means minor flaws, and so on. Your program score is the product of your correctness score (from steps 1 through 4) and the style percentage.
  6. Your writeup will be evaluated separately to produce the remaining points of your project score.

Miscellaneous information

As with project 2, there will be frequent progress reports and high-level design discussion for homework. The typical solution to this project is around 1000 lines, and many students find they have to rewrite sections of code to satisfy the efficiency constraints. Start planning soon.

In the ~cs61b/code/proj3 directory is a Checker program that checks whether a given sequence of moves solves a given puzzle. The program takes two arguments, an initial configuration and a goal configuration in the same format as those for Solver.java. It also takes a sequence of moves, in the format to be produced by Solver.java, as standard input. Its output indicates whether the moves solve the puzzle, and if not, why not. On a UNIX system, you might run the program as follows:

	java Solver init goal | java Checker init goal

("Init" and "goal" stand for names of files containing the initial and goal configurations, respectively.)

To use the program, copy the files Checker.class and TrayVerifier.class from ~cs61b/code/proj3. Warning: It doesn't check for extraneous junk characters on a line, instead giving a rather difficult-to-understand error message involving the inability to move.