CIT 594 Assignment 3: Backtracking
Spring 2012, David Matuszek

Purposes of this assignment

To teach backtracking.
To give you a little practice with Java's Stack class and Set interface.

General idea of the assignment

Write a program to read in and solve path-finding puzzles. Each puzzle consists of a sequence of integers, like this:

The orange color on the first square indicates your current position. At each step in the puzzle, you may move exactly the number of squares indicated by the integer in the square you are in. You may move either left or right along the row but may not move past either end. For example, the only legal first move is to move three squares to the right because there is no room to move three spaces to the left. The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves:

Starting position

Step 1:
Move right

Step 2:
Move left

Step 3:
Move right

Step 4:
Move right

Step 5:
Move left

Step 6:
Move right

Even though this puzzle is solvable—and indeed has more than one solution—some puzzles of this form may be impossible, such as the following one:

In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares.

Details

You may assume that there are no negative numbers in the given array.

You may not assume:

The last location in the array contains a zero. (If you can get there, it's irrelevant what number it contains.)
There are no zeros elsewhere in the array. (There might be, and if you go there you are stuck.)
There is a legal move from every location in the array. (One of the above arrays might contain a 20, for example.)

You may not change the numbers in the array.

Write the following methods, with the exact signatures specified:

public static Stack<Character> solve(int[] puzzle): Takes an array of integers such as in the above examples, and tries to find a path from the first location in the array (puzzle[0]) to the last location in the array (puzzle[puzzle.length - 1]). No location in the array may be entered more than once. A move to the left will be represented by the capital letter 'L'; a move to the right will be represented by the capital letter 'R'. The top value on the stack is the first move.

Returns a null value (instead of a Stack) to indicate that there is no solution.
public static Set<Stack<Character>> findAllSolutions(int[] puzzle): Input and solution requirements are the same as for solve, but this method finds and returns all such solutions. If there are no solutions, an empty set is returned.

Unit test these methods.

Notes:

We use a Stack for the solution because that is the easiest way to do it. You can create a stack when you find a solution (reach the end of the array), and fill the stack as you return out of the recursion. The stack will then hold the solution in an order that's easy to use.
No main method is required. However, if you decide to write one, use a JFileChooser to allow the user to select a file containing one or more puzzles of this sort. The file should contain one puzzle per line, as a list of integers separated by spaces.
This assignment is borrowed, with modifications, from an assignment in CS106B at Stanford, taught by Julie Zelenski.

Structure of the assignment

Project name: Backtracking
Package name: backtracking
Class names and method signatures:
- class Backtracking
  - public static Stack<Character> solve(int[] puzzle)
  - public static Set<Stack<Character>> findAllSolutions(int[] puzzle)
Provide JUnit tests for both solve and findAllSolutions.
Provide Javadoc documentation for the Backtracking class and all methods in it.

Due date

Your program is due before 6am Tuesday, February 6. Zip up the entire directory for this project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.