Before we begin, please note that this is a group project. Please work in a group of total size 3 or 4. Your code will not be accepted if turned in solo. Groups of 2 may be allowed if granted permission from your TA.

First, download some files for this project here.

A. Background Information

For this project, you will be writing a program to solve sliding block puzzles. These puzzles consist of a number of rectangular blocks in a tray. The goal is to slide the pieces without lifting any out of the tray until a certain configuration is achieved. An example (from Winning Ways, E.R. Berlekamp et al., Academic Press, 1982) is shown below:

To try out one of these puzzles for yourself, you can try out these online web apps: Pennant, Red Donkey

Formatting

Blocks are represented by their top-left coordinate and their bottom-right coordinate. For example, the block at the top-left corner of the tray configuration above has its top-left coordinate at 0 0, and has its bottom-right coordinate at 1 0. Thus, this block is represented by the line:

0 0 1 0

The 2 × 2 block in the tray configuration above is represented by the line:

1 1 2 2

Tray configuration files represent trays and all of the blocks contained in a tray. The first line of every tray configuration file will have two positive integers: the height and the width of the tray (separated by a single space character). All subsequent lines of each tray configuration will have four space-separated non-negative integers that represent a block. Blocks can appear in the tray configuration file in any order. You may assume that the length and width of a tray are no greater than 256 each.

The tray configuration on the previous page can be represented by a file containing the following:

5 4
0 0 1 0
0 3 1 3
2 0 3 0
2 3 3 3
1 1 2 2
3 1 3 2
4 0 4 0
4 1 4 1
4 2 4 2
4 3 4 3

Goal configuration files are similar to tray configuration files, except they don’t specify the dimensions of the tray. Instead, each line of a goal configuration file specifies the position of a block. In the example above, if our goal was to move the 2 × 2 block two spaces down in the tray configuration above (and we didn’t care where any of the other blocks were), our goal configuration file would contain the single line:

3 1 4 2

If we also wanted to have other blocks at other positions, we would have more lines in our goal configuration file. Note that if there were multiple 2 × 2 blocks in the initial configuration, any of the 2 × 2 blocks can be at the specified position to satisfy the goal file example above.

Each move is represented by four non-negative space-separated integers. The first two integers make up the current top-left coordinate of the block we want to move. The last two integers make up the top-left coordinate of where we want the block to be after we execute the move. In the example above, if you wanted to move the 2 × 2 block up one space, you would output the move:

1 1 0 1

If you wanted to make more moves, your program would output more lines of moves.

B. Solver

Write a Solver.java program that prints moves to stdout (this is what happens when you use System.out.println), one move per line. Your program should take in command line arguments as follows:

java Solver init goal

where init is an initial tray configuration file, and goal is a goal configuration file.

Your Solver must be bullet proof, that is, it should not crash for any reason. There are only three things that are allowed to happen when you run Solver:

• There is a solution that leads from init to goal, in which case your solution should print it out.
• init and goal are valid files, but there is no sequence of moves that can solve the problem. In this case, your program should just print print nothing, but exit normally.
• anything else (e.g. init and goal are formatted incorrectly, the user doesn't specify an init, etc). In this case, your program should just print out Invalid init and/or goal file.

We gave you a Checker class that checks whether your solution is correct. Pipe the output of Solver into Checker to see if your solutions is valid:

java Solver init goal | java -jar Checker.jar init goal

Your Solver program will be graded on time efficiency (see the “Grading” section below). The amount of space your program needs, however, is not an important consideration, except that your program has to fit in the default allocation of memory provided on the instructional computers.

C. Readme

You must also include with your submission a file readme.pdf (must be a PDF, not just a text file). This is worth a significant portion of your project grade. Your readme file should include the information listed below, answering all of the questions in each category:

• Division of labor (half a page): An explanation of how your team split the work for this assignment among your team members, and why you split it this way.
• Design (2 - 3 pages): A description of the overall organization of your submitted program (algorithms and data structures) that lists operations on blocks, trays, and the collection of trays seen earlier in the solution search. Diagrams will be useful here to show the correspondence between an abstract tray and your tray implementation. This description should contain enough detail for another CS 61BL student to understand clearly how the corresponding code would work.

• Experimental results (1 - 2 pages per experiment): Three experiments comparing results of a design choice from the project. Each experiment should include the following sections and content, written in a way that a fellow CS 61BL student would understand:

  • Summary: description of the test and the results
  • Results: graphs and/or tables with the results of the test
  • Conclusions: explanation and interpretation of the results

  Here are some questions to get you thinking about appropriate tests:

  • What data structure choices did you consider for the board? What operations did you optimize? (Generation of possible moves? Comparison of the current configuration with the goal? Making a move?) How did these considerations conflict?
  • If you used a data structure that involved hashing, how did you choose a hash function for the boards? How did you your choice opitmize the need for fast computations, minimal collisions, and economical use of memory?
  • How did you choose between moving blocks one square at a time and making longer block moves?
  • How did you choose between breadth-first and depth-first (or some best-first) searching of the graph of move sequences? If you took a different approach, what was it and why did you take that approach?

• Program Development (1 page): An explanation of the process by which you constructed a working program.

  • What did you code and test first, and what did you postpone?
  • Why did you build the program in this sequence?
  • How did your team test your program ?What test cases did you use for each of your classes, and how did you choose them?
• Disclaimers: In this section, describe parts of your solution that don't work, if any. You will lose fewer points for bugs in your project that are listed here.
• Improvements (half a page): If you were to make one more improvement to speed up your program, what would it be, and what is your evidence for expecting a significnat speedup?

Students and software engineers are expected to write design documenation in industry and in courses such as CS 162 and CS 169, so you might as well get practice with them now!

D. Submission

Submit project 3 on an instructional machine with the command submit proj3 by Tuesday, 11 August. As with project 2, you must submit with a team of 3 - 4. Your submission must include the following files:

• Solver.java
• readme.pdf

and any other Java files you wrote for this project. Only one member should submit per team.

At the end of the project, there will also be a group evaluation form, just like with project 2. Please look out for it. Project grades may be adjusted based on these responses.

E. Grading

This project is worth 30 course points. The grade breakdown is as follows:

• Code: 16

  • 4 points for correctly solving all of the easy puzzles in under 80 seconds each. See easy.csv for a complete listing of all easy puzzles. This is all or nothing.
  • 0.3 points per hard puzzle solved in under 80 seconds of CPU time (capped at 8 points total). See the script run.hard for a complete listing of all hard puzzles. In addition, note that CPU time is not exactly the same as real elapsed time. Again, use run.hard to get an accurate measurement.
  • 4 points for bullet proofing your code.
• Readme: 10
• Checkpoint: 4 (more on this below)

F. Checkpoint

There will be a project checkpoint in lab the Thursday before the project is due. To receive full points, your team must demonstrate to your TA that your Solver program can solve all the easy puzzles (though it may not be able to solve hard puzzles quickly). Your team must also have a draft of your readme.pdf, specifically the "Divison of labor" and "design" portions. In addition, every member of the team must be prepared to answer questions for the TA on any part of the project. People will be picked randomly to answer questions, and the whole team's grade will depend on how each person does.

G. Helper Scripts

The staff has provided some scripts you can use to help test your program. The scripts run.easy, run.medium, and run.hard will run Solver and Checker against all the easy, medium, or hard puzzles. To use the scripts, make sure they're in the same directory with your Checker.jar, the directories with easy, medium, and hard puzzles, and your compiled Solver.class. Then, you may have to change the permissions of the script:

chmod +x run.easy

Run the scripts via the terminal. For example, if you want to run all of the easy puzzles, you would type

./run.easy

Each script will print out Verified for each puzzle your program sucessfully passes (either solves correctly or detects that there is no solution), and some sort of error message for every puzzle your program fails.

In order to get the scripts to run, you may have to change the first line of each script to the location of your bash interpreter. Type which bash at the terminal. Then make sure the first line is the output of which bash prefixed by #!.

If you can't figure out how to get the scripts to work, you are encouraged to use your favorite search engine to learn why.

Warning: Running the scripts on your computer may be misleading if your computer is faster than the instructional machines. Your code will be graded based on our measured runtimes, not your own. Be sure to test out on the instructional machines! Specifically, test out on the hive machines (hive1.cs.berkeley.edu, hive2.cs.berkeley.edu, hive3.cs.berkeley.edu, etc.), not on torus.cs.berkeley.edu, or cory.eecs.berkeley.edu.

H. FAQ

Q: Can blocks move diagonally?

A: No. Only up, down, left, or right.

Q: Can a block move more than one space at a time?

A: Yes, a single move can move a block any number of spaces in a single direction as long as there are no other blocks in its path.

I. Collaborative Contest!!

Many CS classes like to end with a final contest that pits students against each other in a challenge to do the best on their project and earn extra credit. In fact, this very class used to end with the same: whichever team had the fastest block puzzle solver overall earned extra credit.

However, in the spirit of collaboration over competition that 61BL hopes to foster, the extra credit will now be collaborative by lab section. Here's how it works:

There is a set of extra, unreleased puzzles. Each group's submission will be run for a certain amount of time against these puzzles. The total number of puzzles all the groups in your lab solves contribute to the extra credit your lab gets. This is normalized to the number of groups in your lab. This isn't a competition between labs — all labs can earn the full points if they do really well.

The max extra credit you can earn out of this is two points. You may earn fractions of points. Do your best to contribute and help your lab succeed! If enough students submit early, we can release scores from these puzzles early, so you will have a chance to resubmit and do better. As a warning, earning the full two points will be quite difficult (your lab will have to collaboratively match the staff solutions' time to get the full 2), so it's in your best interest to submit early and see how well you do!

By the way: the same rules about cheating as always still apply. You shouldn't talk to other groups about how you're approaching your solution. Just keep in mind that by going above and beyond to make a really fast solver, you're helping to contribute to something greater than yourself!