CIT 594 Assignment 7: Backtracking
Spring 2012, David Matuszek

# Purposes of this assignment

• To teach backtracking.
• To teach enums, in case you haven't already seen them.
• To give you a break! (It's time for an easy 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:

• 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. (The above array might contain a `20`, for example.)
• There are no cycles.

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:

• Use backtracking!
• 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 the correct order.
• You may not modify the given array, nor make a copy of the array.
• No `main` method is required.
• This assignment is inspired by 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:
• `enum Direction`
• `class Pathfinder`
• `public static Stack<Direction> solve(int[] puzzle)`
• `class PathfinderTest`
• Unit tests for `solve`, and any other methods you might need.
• Provide Javadoc documentation for the `Pathfinder `class and all methods in it.

# 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.