CIT 594 Assignment 3: Backtracking
Spring 2012, David Matuszek

Purposes of this assignment

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:

3 6 4 1 3 4 2 5 3 0

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
3 6 4 1 3 4 2 5 3 0
Step 1:
Move right
3 6 4 1 3 4 2 5 3 0
Step 2:
Move left
3 6 4 1 3 4 2 5 3 0
Step 3:
Move right
3 6 4 1 3 4 2 5 3 0
Step 4:
Move right
3 6 4 1 3 4 2 5 3 0
Step 5:
Move left
3 6 4 1 3 4 2 5 3 0
Step 6:
Move right
3 6 4 1 3 4 2 5 3 0

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:

3 1 2 3 0

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:

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:

Structure of the assignment

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.