Stephen Weiss
Computer Science
University of North Carolina at Chapel Hill
CB# 3175, Sitterson Hall
Chapel Hill, NC 27599-3175
weiss@cs.unc.edu

We cover backtracking as one of a set of problem solving strategies toward the end of our CS-2 course.  I'm always looking for interesting problems that can be solved by backtracking and that yield significant economies with pruning.  In the past I've used:

        *  map coloring (given an adjacency matrix and a palette, how many different  ways are there to color a map so
            that no adjacent regions are the same color?)
         *  making change (how many ways are there to make change for a given amount – I awarded a cash prize of
             $1.91 to the person who solved the problem most efficiently.)
         * solving a word jumble
         * solving a cryptogram (or at least coming up with a set of words that meet certain criteria.)
         * finding what two English words add up to "stuff" where 'a' is 1; 'b' is 2, ... 'z' is 26, and addition is letter by letter.
           The answer is "mecca" and "force."

Here's this years edition of the backtrack problem.  It's a very simple puzzle – just arrange the nine squares so that the edges that touch each add to zero.  There are 95,126,814,720 ways to arrange the squares (9!*4⁹) and four solutions (actually only one solution with four orientations).  Other puzzles (text files called Datai.txt, where i = 1...6) have more solutions.

The program combines a number of important course concepts:
         backtracking and recursion
         pruning
         algorithm analysis (I have the student instrument the program to determine both running time and number of
                  calls to the various methods.)
         building appropriate data structures (including a Card class, a Board class to represent the board, and a
                  Pool class to hold cards not yet placed on the board.)
         generalizes both to larger boards and to 3 dimensions (cubes with numbers on each face)

We have pretty standard grading criteria stressing correctness, clarity, and documentation.  We also look for appropriate choice of classes and division of function.  For this problem, we also grade on efficiency giving higher grades to programs that solve the problem with the fewest number of tests.

The program is appropriate for CS-2.  It is actually pretty easy if the problem is segmented properly.  My backtrack method is about 15 lines of code (excluding comments and lines that contain only an opening or closing bracket).  The filtering methods (that determine whether or not it's ok to add a specified card with a specified orientation to the board) contain a total of about 20 lines of code.  But solving the problem requires a real understanding of backtracking, pruning and real comfort with recursion.  I generally allow about 10-12 days for this assignment, but it is at the end of the semester when students are particularly busy in other courses.  I plan to give them the puzzle at the beginning of the semester and let them play with it for a while.

Major disadvantage is that not all CS-2 courses cover backtracking.

Links
    Puzzle
    Executable (for download)
    Data files
    SIGCSE 03 paper (MS Word, 4 pages)
    PowerPoint presentation
    Link to chapter on brute force and backtracking
 
 

Note: I call a puzzle "perfect" if each puzzle piece has the numbers 1, 2, 3, and 4 with two positive and two negative.  Puzzle 1 (the one in the picture and Data1.txt) is not perfect; the other puzzles are perfect.  The sample program checks the puzzle for perfection.
 
 

Extra info about this assignment: