CIT 594 Assignment 4: Backtracking
Spring 2015, David Matuszek

Purposes of this assignment

• To teach backtracking.
• To give you some 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 end of the row. In this configuration, you can solve the puzzle by making the following set of moves:

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:

• The array length is nonzero.
• There are no negative numbers in the 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.)
• There are no loops. (For example, the array might be 3 1 2 3 0 .)

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:

• 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.
• Provide estimates of your time: How much time you think this assignment will take, and how much it actually took.

Due date