Objectives: This programming exercise will provide experience using recursion to solve a moderately difficult programming problem.

Program Description: The user will be presented with the following menu:

*** Select a Maze ***

Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

0 Quit

After choosing an option, the program should attempt to find a path through the requested maze. The program will provide specific mazes for options 1 4.

The program will display the initial maze including the maze dimensions and attempt to find a path through the maze.

If a path is found, the message *** SOLVED *** will be displayed followed by a display of the maze with the valid path clearly marked.

o The number of steps to move from the start point of the maze to the end point of the maze will also be

shown.

If a path cannot be found, the message *** NOT SOLVED *** should be displayed. See the pages 4-7 of this assignment sheet for sample program output from this program.

A sample maze: # specifies a wall in the maze and . specifies an open path:

# # # # # # # # # # #

. . . # . . . . . . #

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

# # . # . . . . # . #

. . . . # # # . # . .

# # # . # . # . # . #

. . # . # . # . # . #

# . # . # . # . # . #

. . . . . . . . # . #

# # # # # . # # # . #

. . . . . . # . . . #

# # # # # # # # # # #

The sample maze solved: O indicates the path taken:

# # # # # # # # # # #

O O O # O O O O O O # O O # O # O # # # # O #

# # O # O O O O # O #

. . O O # # # O # O O

# # # O # . # O # . #

. . # O # . # O # . #

# . # O # . # O # . #

. . . O O O O O # . #

# # # # # . # # # . #

. . . . . . # . . . #

# # # # # # # # # # #

A total of three classes are required for this program.

Maze.java The class defining the Maze object. A starter file is provided changes required.

Menu.java Reused from the previous programs. Provided - No changes required.

TestMaze.java The class containing the main method providing the user interface. Not provided.

File 1: Maze.java UML DIAGRAM FOR AND DISCUSSION FOR Maze.java

Note: A shell of the Maze.java file is provided containing the data members required for this class. See Maze.java posted to Blackboard with this assignment file.

Maze

MAZE1_ROWS : Integer = 12

MAZE1_COLS : Integer = 12

MAZE1_ENTERROW : Integer = 2

MAZE1_EXITROW : Integer = 4

MAZE1[MAZE1_ROWS][MAZE1_COLS] : Character[][] (see provided Maze.java file for contents of MAZE1)

MAZE2_ROWS : Integer = 8

MAZE2_COLS : Integer = 12

MAZE2_ENTERROW : Integer = 6

MAZE2_EXITROW : Integer = 1

MAZE2[MAZE2_ROWS][MAZE2_COLS] : Character[][] (see provided Maze.java file for contents of MAZE2)

MAZE3_ROWS : Integer = 9

MAZE3_COLS : Integer = 9

MAZE3_ENTERROW : Integer = 4

MAZE3_EXITROW : Integer = 3

MAZE3 [MAZE3_ROWS][MAZE3_COLS] : Character [][](see provided Maze.java file for contents of MAZE3)

maze [] [] : Character [] []

rows : Integer

cols : Integer

enterRow : Integer

exitRow : Integer

steps : Integer

<> Maze(mazeNum : Integer)

printMaze()

traverseMaze()

- findPath(row : Integer, col : Integer) : Boolean

Note: Capital letters indicate final or constant values in the UML diagram.

Discussion of the Maze Class:

Data Members:

MAZE1_ROWS, MAZE2_ROWS, MAZE3_ROWS

The number of rows in the specified sample maze

MAZE1_COLS, MAZE2_COLS, MAZE3_COLS

The number of columns in the specified sample maze

MAZE1_ENTERROW, MAZE2_ENTERROW, MAZE3_ENTERROW

The row number to enter the specified sample maze (column entry point will always be column zero)

MAZE1_EXITROW, MAZE2_EXITROW, MAZE3_EXITROW

The row number to exit the specified sample maze (column exit point will always be columns 1

MAZE1, MAZE3, MAZE 3 : Character [][]

Three sample mazes provided for testing purposes

maze [] [] : Character [][]

Two dimensional array to store the maze to be traversed

rows : Integer

Number of rows in the maze to traverse

cols : Integer

Number of rows in the maze to traverse

enterRow : Integer

Row to enter maze (start column will always be 0) for the maze to traverse

exitRow : Integer

Row to exit maze (exit column will always be at cols-1) for the maze to traverse

steps : Integer

Counter to hold the number of steps required to traverse the valid path through the maze

Methods:

<> Maze(Integer mazeNum)

Assigns the maze, rows, cols, enterRow, exitRow according to the mazeNum parameter value

+ printMaze()

Display the number of rows and columns in the maze

o Display the maze to the screen

See the sample program execution shown on pages 5-9 of this assignment for display format.

+ traverseMaze()

Non-recursive method to begin the maze traversal

Calls findPath(enterRow, 0) to begin the traversal of this maze

If findPath returns true display the *** SOLVED *** message followed by the maze showing the path through the maze

Else display the *** NOT SOLVED *** message

findPath(row : Integer, col : Integer) : Boolean

Recursive method to attempt to find a path through the maze

o Base Case 1: If the row = exitRow and col = cols-1, the maze is solved return true

o Base Case 2: If the value at row/col is a wall (#) there is no path at this position return false

General/Recursive Case: Attempt to find a path from the current row and col position.

A node that is part of the path must be changed from the . to a O (capital letter O)

Assignment: Design the recursive algorithm to search the possible paths from this node in the maze recursively. (Hint: you will need to check in each of the four directions if a valid path has NOT been found)

Track the number of steps in the valid path. The steps should only reflect the actual number of steps through a valid path not all the steps the algorithm tried.

If a path is not found at row, col of the array, set the maze[row][col] back to the original value stored (.) This will ensure that only the valid path through the maze will be shown in

the final, traversed maze

A discussion of a similar (although not exact) algorithm can be found at: http://www.cs.bu.edu/teaching/alg/maze/

File 2: Menu.java

This file may be used without changes from the previous programs. See previous programs for samples of creating, initializing the menu options and running the menu.

File 3: TestMaze.java

Create a Menu object using the sample menu display shown above and on pages 4-7 of this assignment.

While the user does not want to quit:

o Display the menu and read the users choice

If the user does not choose quit:

Create a Maze object using the menu option as the maze type passed to the Maze constructor

Call the Mazes traverseMaze method to traverse this maze

SUMMARY OF ASSIGNMENT / HOW TO COMPILE

1. Create the directory for this assignment as defined below: mkdir SPRING2016-CSCI-1620-006-P2

Change directories to the directory using the cd command: cd SPRING2016-CSCI-1620-006-P2

Copy the Menu.java file and the shell of the Maze.java file provided with this assignment to your directory on loki.

Edit or create the required Java files as described above.

Once these steps are completed, test your progress by compiling the program.

[user@loki.user]$ javac Menu.java

[user@loki.user]$ javac Maze.java

[user@loki user]$ javac TestMaze.java

[user@loki user]$ java TestMaze

Required Elements:

Program output should match the output shown on the following pages

All outputs to the user must include identifying text, and the user should be prompted for all inputs.

IMPORTANT: If there is more than one valid path through the maze, your answer may be slightly different than that shown by the sample program execution. The order in which the possible paths are checked effects the final path traversed.

SAMPLE PROGRAM EXECUTION The only user input is the input of the menu option aashokan@loki:~/workarea/1620/P2$ java TestMaze

*** Select a Maze*** Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

Quit Option: 1

BEFORE TRAVERSAL:

This maze is size: 12 x 12

# # # # # # # # # # #

. . . # . . . . . . #

. # . # . # # # # . #

. # . # . . . . # . #

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

# # # . # . . . # . #

. . # . . . # # # . #

# . # . # # # . # . #

. . . . . . . . # . .

# # # # # . # # # . #

. . . . . . # . . . #

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

*** SOLVED ***

AFTER TRAVERSAL:

This maze is size: 12 x 12

# # # # # # # # # # #

O O O # O O O O O O #

O # O # O # # # # O #

O # O # O O O O # O # O O # O O # # # O # O #

# # # O # O O O # O #

. . # O O O # # # O #

# . # . # # # . # O #

. . . . . . . . # O O

# # # # # . # # # . #

. . . . . . # . . . #

# # # # # # # # # # #

Steps in Path: 38

Select a Maze*** Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

Quit Option: 2

BEFORE TRAVERSAL:

This maze is size: 8 x 12

# # # # # # # # # # #

. . . # . . . # # . .

. # . . . # . . . . #

. # # # # . # . # . #

. . . # # . . . . . #

# # . # # # # . # . #

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

# # # # # # # # # # #

*** SOLVED ***

AFTER TRAVERSAL:

This maze is size: 8 x 12

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

Assignment-2

. . . # . . . # # O O

. # . . . # . . . O #

. # # # # . # . # O #

. . . # # . . O O O #

# # . # # # # O # . # O O O O O O O O O . # #

# # # # # # # # # # #

Steps in Path: 17

Select a Maze*** Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

Quit Option: 3

BEFORE TRAVERSAL:

This maze is size: 9 x 9

# # # # # # # #

. # . # . . . #

. . . # . # # #

# # . # . # . .

. . . . . . # . #

# . # . # # . #

. . # . # . . #

# . # . # . . #

# # # # # # # #

NOT SOLVED ***

Select a Maze*** Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

Quit Option: 4

BEFORE TRAVERSAL:

This maze is size: 12 x 12

# # # # # # # # # # #

. . . # . . . . . . #

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

# # . # . . . . # . #

. . . . # # # . # . .

# # # . # . # . # . #

. . # . # . # . # . #

# . # . # . # . # . #

. . . . . . . . # . #

# # # # # . # # # . #

. . . . . . # . . . #

# # # # # # # # # # #

*** SOLVED ***

AFTER TRAVERSAL:

This maze is size: 12 x 12

# # # # # # # # # # #

O O O # O O O O O O # O O # O # O # # # # O #

# # O # O O O O # O #

. . O O # # # O # O O

# # # O # . # O # . #

. . # O # . # O # . #

# . # O # . # O # . #

. . . O O O O O # . #

# # # # # . # # # . #

. . . . . . # . . . #

# # # # # # # # # # #

Steps in Path: 36

Select a Maze*** Choose from the following options:

Maze 1

Maze 2

Maze 3

Maze 4

Quit

Option:0