The program for this assignment solves sliding blocks puzzles. Rectangular blocks are arranged in a tray, and must be slid horizontally or vertically to form a given configuration. An example is here.
Here are the clancy-blox-presentation.pdf slides from Mike's talk about this nifty assignment.
Accompanying the assignment are a collection of "easy" puzzles and a collection of "hard" puzzles, together with UNIX shell scripts to run the program on all the puzzles in each collection. Grading the program involves first running it on the easy puzzles. If it solves almost all of them, students can then earn extra points for each hard puzzle their program solves.
The full assignment is here.
This assignment is essentially a term project for the end of CS 2. Its prerequisites are familiarity with backtracking search, breadth- and depth-first tree traversal, priority queues, and hashing. In our semester-long (15 weeks) CS 2, we give students around a month to work on the project. Most submissions are around 1000 lines of code.
Computers these days are much too fast. Back when I first started teaching, it wasn't too hard to find applications where "dumb" algorithms were just too slow. Now, for example, linear search through a 20,000-word dictionary takes only a small fraction of a second. This assignment, however, puts a premium on intelligent choice of data structures. Some of the hard puzzles may involve upwards of 100,000 board configurations.
Moreover, project requirements may easily be adjusted to accommodate faster/bigger computers. The problem statement allots two minutes per puzzle solution and requires solution of ten hard puzzles for full credit. In our fall 2005 course offering, this resulted in 50 out of 63 submissions being eligible for the hard puzzle points; 33 of those 50 solved ten hard puzzles to earn full credit for correctness/efficiency. The lab computers were 2 GHz Pentium 4's gigahertz with 512 MB of RAM, running Solaris. The Java interpreter, I believe, defaults to 64M heap space and 512K stack space.
The grading encourages incremental development. If a program doesn't work on almost all the easy puzzles, it loses all credit for the hard puzzles, even if it could solve them all. Correct execution is thus a high priority.
The grading also encourages modular design. The typical student can fairly easily produce an initial solution that works on most of the easy puzzles, but then is surprised to find that it fails miserably on the hard ones. The student must then identify and deal with efficiency bottlenecks; this is much easier if the program has been organized to allow plug-and-play experimentation.
A student can get full credit without solving all the hard puzzles. However, hotshots can take on the challenge of solving more than the minimum required.
The design space is quite large. Some efficiency constraints conflict with others. Efficiency issues include the following:
There are several reasonable solutions to all these questions. (Work in partnership is a good idea; two heads are usually better than one at coming up with solutions.)
I've assigned this project several times, and have removed most of the bugs. There is a lot of support software: 57 easy puzzles, 41 medium puzzles, and and 23 hard puzzles, plus a solution checker and UNIX shell scripts for testing student solutions.
Students enjoy this project. Here are survey results for students in the fall 2005 class.
How much did you learn from the project?
How interesting was the project?
Some student comments:
"I liked project 3 a lot. It was really fun to write it because it was challenging, and we applied a lot of the concepts we learned such as trees and hashes. The fact that you had to think of ways to improve the program and then get to see your results was very rewarding and fun."
"The specifications of the project opened my eyes to how programming would be like outside of classes."
"The third project was interesting in all the possibilities that you could work on for attacking the problem."
"The third one incorporated a bunch of different things: hashing, we got to choose our own data structures instead of being given ways to do it; no framework was provided, and we had to account for efficiency and memory."
"I think the third one was cool because there was so much free rein and you had to brainstorm with a partner."
"I learned the most from project 3. I did a lot of independent research on algorithms and learned a lot about some that are used today. Very fun! I look forward to taking cs170 [the junior-level algorithms course] now."
"Completing project 3 gave me a sense of 'wow I can't believe i programmed something that solves these puzzles!'"
Finally, if an instructor is worried about cheating, solutions on the web, etc., he or she can modify the external representation of a block or a move. In the current assignment, a block is represented by its length and width and the coordinates of its upper left corner. Another representation would be the coordinates of its upper left and lower right corners. Similarly, a move is represented in the current assignment by the coordinates of the upper left corner of the block prior to the move, and the coordinates of that corner after the move. A move could instead be represented using an offset. Changing these representations would necessitate revising all the puzzles and the solution checker, of course, and I haven't done that.
Extra info about this assignment: