Description
This assignment:
Solve for a path through a Two-Dimensional maze by use of exhaustive search and backtracking.
Given a two-dimensional array like the one shown below, create a recursive Java program that will traverse the array looking for a path from the upper left corner to the lower right.
private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,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,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
Program specifications:
In the maze, values represented are:
-
1 – An available space for a path (an open ‘room’)
-
0 – A ‘wall’
-
3 – A visited room
-
7 – A room on a successful path
Your program should:
-
Start in the upper left corner
Eastern Washington University
CSCD211 – Programming Principles II
-
Attempt to move in a direction
-
-
Check that the ‘room’ you want to move into is inside the maze
-
Check that the room you want to move to is available (not a wall)
-
-
-
Check that the room you want to move to has not been visited previously
-
-
If the move is not valid try to move in another direction
-
If the is valid, ‘move’ into the ‘room’ and mark it as ‘visited’ (3)
-
If no valid move is available, unwind in your recursive call stack to the previous call and try the next direction from there
-
Repeat until either you’ve reached the goal or you’ve determined that there is no path through the maze.
Some suggestions:
-
Determine what the base cases will be
-
Your recursive method should return a variable of type boolean.
-
Your recursive method’s signature should accept two parameters only.
To turn in
-
All source files necessary to compile and run program in a jar or zip file named with your last name, followed by first initial of first name, followed by hw6 (e.g.: peterschw6.jar)
-
Name the class that contains your main method MazeTester
Eastern Washington University
