CIT 594 Assignment 7: 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 an NxN array of integers, like this:

7 4 4 6 6 3 2 2 6 8
3 3 6 5 4 3 7 2 8 3
4 1 6 6 2 4 4 4 7 4
4 5 3 4 3 5 4 4 8 5
5 1 4 6 6 5 0 7 1 4
2 6 9 4 9 7 7 9 1 4
3 5 4 0 6 4 5 5 5 6
6 6 2 3 4 7 1 2 3 3
3 5 4 3 6 5 4 5 2 6
3 9 3 5 1 1 5 4 6 6

The problem is as follows: Starting in the upper left-hand corner (location [0][0]), find a sequence of moves that takes you to the bottom right-hand corner (for an NxN array, this would be location [N-1][N-1]). From each location in the array you may move left, right, up, or down; the number in the location tells you exactly how far to move.

For example, location [0][0] contains a 7, so from there you must move exactly 7 squares, either to the right or down. You cannot move up or left, because that would take you outside the array.

To help you see the solution, the squares along the solution path have been colored orange. From 7 you move right to 2, down to 4, down to 5, up to 5, etc. The complete solution is
     [(0, 0), (0, 7), (2, 7), (6, 7), (1, 7), (1, 5), (1, 2),
      (7, 2), (7, 4), (7, 8), (4, 8), (5, 8), (5, 9), (9, 9)].
(Also, in the example, there are several squares from which you cannot move at all! Can you find them?)

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.

Define the following enum:

public enum Direction { UP, DOWN, LEFT, RIGHT }
An enum is a kind of class you may not have encountered before. It is a kind of class, and you can make one from Eclipse's New... menu. It should be a separate class, in its own file (named Direction.java), not an inner class. This enum defines exactly four constants, which you can refer to in your code as Directon.UP, Direction.DOWN, Direction.LEFT, and Direction.RIGHT, all of which are values of type Direction. This class has some associated methods, which you can read about if you are interested.

Programming hint: You can save yourself some typing by assigning these constants to variables in your program, for example,
Direction left = Direction.LEFT;

Write the following method:

public static Stack<Direction> solve(int[][] puzzle)
Takes an NxN array of integers such as in the above example, and tries to find a path from location [0][0] to location [N-1][N-1]. Returns a stack of directions. The top value on the stack is the first move. In the above example, the top of the stack will be Direction.RIGHT, followed by Direction.DOWN, etc.

The method should return null if there is no solution. If there is more than one solution, just return one (to simplify testing, I will attempt to avoid creating a puzzle with multiple solutions.)

Unit test this method.

Notes:

Structure of the assignment

Due date

Your program is due before 6am Thursday, April 4. Zip up the entire directory for this project, and submit via Canvas.

Because I regard this assignment as particularly short, no extensions will be given.