Objectives

This programming assignment will give you the opportunity to practice using recursion in Java.

Program Description

As shown below, a grid of #s and dots (.) can be used to represent a maze. The #s represent the walls of the maze and the dots (.) represent locations of possible paths through the maze. Note that the dot in the left-most column is the entrance and the dot in the right-most column is the exit. (A maze can only have one entrance and one exit.) A move can only be made to a location in the grid that contains a dot.

Maze Example

###############

#.#..#.####..##

#...#.#....##.#

##..#...#...#.#

###.##...#....#

#.#..#####....#

#.#.###......##

......#.#.#.###

##.#.#....#.#.#

#..#..#....####

###.#.##.....##

###.#.##.#.#...

#...#...#...###

#..##.........#

#....#####.##.#

###############

Both iterative and recursive solutions to maze-solving exist. The outline of a recursive method, solveMaze(r, c) (the parameters r and c represent the row and column of the current cell), is provided below. Note that the algorithm will return to the starting location if no possible solutions exist. One of your tasks in this assignment is to implement this algorithm in order to traverse a maze.

boolean solveMaze(int r, int c)

{

if (current cell is outside the maze)

return false

if (current cell is the exit)

return true

if (current cell not open)

return false

Mark (with a +) current cell as part of the solution path

if (solveMaze(cell below the current cell) == true)

return true

if (solveMaze(cell to the right of the current cell) == true)

return true

if (solveMaze(cell to the left of the current cell) == true)

return true

if (solveMaze(cell above the current cell) == true)

return true

Unmark (with an x) current cell as part of the solution path

return false

}

Two classes are required for this assignment:

netID_Maze A class that defines what a maze is

netID_MazeSolver Holds a netID_Maze, other required data members, the recursive method to solve the maze

UML Diagram for Class netID_Maze

netID_Maze

- map : Char[][]

- entranceRow : Integer

- exitRow : Integer

<> netID_Maze()

<> netID_Maze(map : Char[][], entranceRow : Integer,

exitRow : Integer)

+ getCell(r : Integer, c : Integer) : Char

+ setCell(r : Integer, c : Integer, val : Char) : void

+ getEntranceRow() : Integer

+ setEntranceRow(entranceRow : Integer) : void

+ getExitRow() : Integer

+ setExitRow(exitRow : Integer) : void

+ getRows() : Integer

+ getColumns() : Integer

+ isEntrance(r : Integer, c: Integer) : Boolean

+ isExit(r : Integer, c: Integer) : Boolean

+ isOpen(r : Integer, c: Integer) : Boolean

+ toString() : String

What follows is a short description of what each data member represents and what each method does.

map: Stores a reference to a two-dimension array of chars representing a maze (see description of a maze above).

entranceRow: Stores the row (zero-based) of the entrance. (The entrance is in column 0.) As explained below (see explanations of getEntranceRow() and setEntranceRow()), it must never be accessed directly.

exitRow: Stores the row (zero-based) of the exit. (The exit is in column n 1 where n is the number of columns in the maze.) As explained below (see explanations of getExitRow() and setExitRow()), it must never be accessed directly.

netID_Maze() (no-parameter constructor): Uses random numbers to create a maze to which map is made to refer; uses

setEntranceRow() and setExitRow() to set the values of data members entranceRow and exitRow, respectively. A maze should have random dimensions between 12 and 24 (both inclusive) and does not have to be squareeach dimension should be determined independently. A random entrance and exit (only one of each) should be found, but the entrance must be on the left and the exit must be on the right and neither can be in a corner (e.g., cell (0, 0)). The interior of the maze should be implemented so that there is a 1/3 chance any square is a wall (#) and a 2/3 chance that any square is a path (.).

netID_Maze() (parameterized constructor): Set the data members to the specified values. In particular, sets data member map to refer to parameter map and uses setEntranceRow() and setExitRow() to set the values of data members entranceRow and exitRow, respectively.

getCell(): Predicate method that returns the character in the cell at the specified row (r) and column (c).

setCell(): Predicate method that sets the character in the cell at the specified row (r) and column (c) to the provided value.

getEntranceRow(): Predicate method that returns the value of entranceRow. This method must be used to get the value of entranceRow; entranceRow must not be accessed directly.

setEntranceRow(): Predicate method that sets the value of entranceRow to the specified value. This method must be used to set the value of entranceRow; entranceRow must not be accessed directly.

getExitRow(): Predicate methods that returns the value of exitRow. This method must be used to get the value of exitRow; exitRow must not be accessed directly.

setExitRow(): Predicate method that sets the value of exitRow to the specified value. This method must be used to set the value of exitRow; exitRow must not be accessed directly.

getRows(): Predicate method that returns the number of rows in map[][].

getColumns(): Predicate method that returns the number of columns in map[][].

isEntrance(): Determines whether the cell at the specified coordinates is the entrance.

isExit(): Determines whether the cell at the specified coordinates is the exit.

isOpen(): Determines whether the cell at the specified coordinates is openreturns true if the cell is in bounds and a path (i.e., is a .), false otherwise.

toString(): Overrides Object toString(). Returns a String representation of the maze as shown above.

UML Diagram for Class netID_MazeSolver

netID_MazeSolver

- maze : netID_Maze

- steps : Integer

<> netID_MazeSolver(maze : netID_Maze)

+ solveMaze(r : Integer, c : Integer) : Boolean

+ setSteps(steps : Integer) : void

+ getSteps() : Integer

What follows is a short description of what each data member represents and what each method does. maze: Reference to a netID_Maze object.

steps: The number of steps taken to solve the maze. As explained below (see explanations of getSteps() and setSteps()), it must never be accessed directly.

netID_MazeSolver() (parameterized constructor): Creates a netID_MazeSolver object, making data member maze refer to the maze parameter. setSteps() should be used to set the value of steps to 0.

solveMaze(): The recursive method that solves the maze. (See above for an outline of the algorithm in this method.) The parameters r and c represent the row and column of the current cell. Cells that are on the path to the solution are displayed with a +; cells visited in the maze but not on the path to the solution are marked with an x.

getSteps(): Predicate method that returns the value of steps. This method must be used to get the value of steps; steps must not be accessed directly.

setSteps(): Predicate method that sets the value steps to the specified value. This method must be used to set the value of steps; steps must not be accessed directly.

TEST RUN

Maze 1 before:

############

#...#......#

..#.#.####.#

###.#....#.#

#....###.#..

####.#.#.#.#

#..#.#.#.#.#

##.#.#.#.#.#

#........#.#

######.###.#

#......#...#

############

Maze 1 after:

############

#+++#++++++#

++#+#+####+#

###+#++++#+#

#..++###+#++

####+#.#+#x#

#..#+#.#+#x#

##.#+#.#+#x#

#...+++++#x#

######x###x#

#xxxxxx#xxx#

############

Solved

Path took 50 steps.

Maze 2 before:

############

#...#...##..

#.#...#....#

#.####.#.#.#

#...##.....#

###.####.#.#

..........##

############

Maze 2 after:

############

#xxx#xxx##++

#x#xxx#xxx+#

#x####.#x#+#

#xxx##..+++#

###x####+#x#

+++++++++x##

############

Solved

Path took 37 steps.

Maze 3 before:

#########

#.#.#...#

#...#.###

###.#.#..

......#.#

##.#.##.#

#..#.#..#

##.#.#..#

#########

Maze 3 after:

#########

#x#x#xxx#

#xxx#x###

###x#x#..

xxxxxx#.#

##x#x##.#

#xx#x#..#

##x#x#..#

#########

No solution

Steps needed for solution: 24 steps.

Maze 4 before:

#####################

#.##.###..##..#...#.#

..##..###..#.#..#...#

#..#.#.##..##.#.....#

##.....#.#.#..##.#..#

#.##...#.........#.##

#..#.#...#.......#..#

#..#.#...#.#...#...##

####....#.#.####....#

####.##....#.......##

#.##..##.....#.....##

#..#...#.#..######..#

##...####..##.##...##

##.............###...

#####################

Maze 4 after:

#####################

#.##.###..##..#...#.#

++##..###..#.#..#...#

#++#.#.##..##.#.....#

##+++..#.#.#..##.#..#

#.##+..#.........#.##

#..#+#...#.......#..#

#..#+#...#.#...#...##

####+...#.#.####....#

####+##....#+++....##

#.##+.##...++#+++++##

#..#+..#.#++######+.#

##..+####x+##x##..+##

##..+++++++xxxx###+++

#####################

Solved

Path took 45 steps.