Note: The Maze.java and MazeDriver.java code is provided at the bottom of the question

Part 1: Working with the Scaffolding

1. Download the scaffolding, which is composed of two files: Maze.java and MazeDriver.java

2. Compile and run the program, see what it does

3. Review the code, make sure you understand what it is doing (and why it works)

Part 2: Extending the Scaffolding

1. Modify the toString() method to make it generate a more human-readable output (i.e. using symbols rather than numeric codes). One possible example (use something different), uses . to indicate a part of the path, to indicate clear space, # to indicate obstacles, and - and | to indicate the boundaries.

2. Add a method to the Maze class that will automatically generate a random maze:

a. The input parameters should specify the size of the new maze (i.e. there should be two integer parameters, the number of rows and the number of columns). It should work for any size maze; be sure to test it with sizes up to 40 rows by 80 columns.

b. The Start and Goal positions should be on the outer edges of the maze.

c. The maze should be solvable (i.e. there should be a traversable path from the start to the goal). NOTE: this should be done in a single pass (i.e. dont just generate random mazes over and over until you get one thats solvable).

d. You can use either recursion or iteration, whichever seems easier to you.

3. Add a new constructor to the Maze class that takes in a number of rows and a number of columns, and then generates a new random maze of that size (it should call the method you just wrote).

4. Modify the Driver class to test all these things (and demonstrate that they work). Note that you should test each feature as you work on it; dont wait until the end to start testing things!

//******************************************************************** // Maze.java // // Represents a maze of characters. The goal is to get from the // top left corner to the bottom right, following a path of 1s. //******************************************************************** public class Maze { private final int OBSTACLE = 0; private final int CLEAR = 1; private final int START = 2; private final int GOAL = 3; private final int TRIED = 5; private final int PATH = 7; private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1}, {2,0,1,1,1,0,1,1,1,1,0,0,1}, {0,0,0,0,1,0,1,0,1,0,1,0,0}, {1,1,1,0,1,1,1,0,1,0,1,1,1}, {1,0,1,0,0,0,0,1,1,1,0,0,1}, {1,0,1,1,1,1,1,1,0,1,1,1,1}, {1,0,0,0,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,3,0,1,1} }; //----------------------------------------------------------------- // Attempts to solve the maze; this function finds the starting // location and then calls the recursive helper function with // that as the initial location //----------------------------------------------------------------- public boolean solve () { for (int r = 0; r < grid.length; ++r) for (int c = 0; c < grid[r].length; ++c) if (grid[r][c] == START) return traverse(r, c); // if we find a starting location, try to traverse the maze // if we get here, it means there was no starting location return false; } //----------------------------------------------------------------- // Attempts to recursively traverse the maze. Inserts special // characters indicating locations that have been tried and that // eventually become part of the solution. //----------------------------------------------------------------- private boolean traverse (int row, int column) { boolean done = false; if (valid (row, column)) { if (grid[row][column] == GOAL ) done = true; // the maze is solved else { grid[row][column] = TRIED; // this cell has been tried done = traverse (row+1, column); // try down if (!done) done = traverse (row, column+1); // try right if (!done) done = traverse (row-1, column); // try up if (!done) done = traverse (row, column-1); // try left } if (done) // this location is part of the final path grid[row][column] = PATH; } return done; } //----------------------------------------------------------------- // Determines if a specific location is valid. //----------------------------------------------------------------- private boolean valid (int row, int column) { boolean result = false; // check if cell is in the bounds of the matrix if (row >= 0 && row < grid.length && column >= 0 && column < grid[row].length) // check if cell is not blocked and not previously tried if (grid[row][column] == CLEAR || grid[row][column] == START || grid[row][column] == GOAL ) result = true; return result; } //----------------------------------------------------------------- // Returns the maze as a string. //----------------------------------------------------------------- public String toString () { String result = " "; for (int row=0; row < grid.length; row++) { for (int column=0; column < grid[row].length; column++) result += grid[row][column] + ""; result += " "; } return result; } }

//******************************************************************** // MazeDriver.java // // Demonstrates recursion. //******************************************************************** public class MazeDriver { //----------------------------------------------------------------- // Creates a new maze, prints its original form, attempts to // solve it, and prints out its final form. //----------------------------------------------------------------- public static void main (String[] args) { Maze labyrinth = new Maze(); System.out.println (labyrinth); if (labyrinth.solve()) System.out.println ("The maze was successfully traversed!"); else System.out.println ("There is no possible path."); System.out.println (labyrinth); } }