CIT 594 Assignment 4: Backtracking
Spring 2015, 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 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:

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

Turn your assignment in to Canvas before 6 a.m. Tuesday, February 10. Late programs, even if only a minute late, will be penalized 5 points per day, up to a maximum penalty of 50 points. Programs may not be accepted after grades have been published.