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^{9}) and four solutions (actually
only one solution with four orientations). Other puzzles (text files
called Data*i*.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: