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

• 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 youve reached the goal or youve 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 methods signature should accept two parameters only.

• Name the class that contains your main method MazeTester