Solve the maze problem that Project 10 in Chapter 5 describes ( the full description is provided at the end of this question for you ) , using the following recursive algorithm rather than a stack-based one. This algorithm involves backtrackingthat is, retracing your steps when you reach an impasse. Step 1: First check whether you are at the exit. If you are, youre done (a very simple maze); if you are not, go to step 2. Step 2: Try to move to the square directly to the north by calling the method goNorth (step 3). Step 3: If goNorth was successful, you are done. If it was unsuccessful, try to move to the square directly to the west by calling the method goWest (step 4). Step 4: If goWest was successful, you are done. If it was unsuccessful, try to move to the square directly to the south by calling the method goSouth (step 5). Step 5: If goSouth was successful, you are done. If it was unsuccessful, try to move to the square directly to the east by calling the method goEast (step 6). Step 6: If goEast was successful, you are done. If it was unsuccessful, you are still done, because no path exists from the entrance to the exit. The method goNorth will examine all the paths that start at the square to the north of the present square as follows. If the square directly to the north is clear, is inside the maze, and has not been visited before, move into this square and mark it as part of the path. (Note that you are moving from the south.) Check whether you are at the exit. If you are, youre done. Otherwise, try to find a path to the exit from here by trying all paths leaving this square except the one going south (going south would put you back in the square from which you just came) as follows. Call goNorth; if it is not successful, call goWest and, if it is not successful, call goEast. If goEast is not successful, mark this square as visited, move back into the square to the south, and return. The following pseudocode describes the goNorth algorithm: goNorth(maze, creature) { if (the square to the north is clear, inside the maze, and unvisited) { Move to the north Mark the square as part of the path if (at exit) success = true else { success = goNorth(maze, creature) if (!success) { success = goWest(maze, creature) if (!success) { success = goEast(maze, creature) if (!success) { Mark square visited Backtrack south } } } } } else success = false return success } The goWest function will examine all the paths that start at the square to the west of the present square as follows. If the square directly to the west is clear, is inside the maze, and has not been visited before, move into this square and mark it as part of the path. (Note that you are moving from the east.) Check whether you are at the exit. If you are, youre done. Otherwise, try to find a path to the exit from here by trying all paths leaving this square except the one going east (this would put you back in the square from which you just came) as follows. Call goNorth; if it is not successful, call goWest; if it is not successful, call goSouth. If goSouth is not successful, mark this square as visited, move back into the square to the east, and return. The methods goEast and goSouth are analogous to goWest and goNorth. The maze described in CH 5 project 10 (Gaming) Do you know how to find your way through a maze? After you write this program, you will never be lost again! Assume that a maze is a rectangular array of squares, some of which are blocked to represent walls. The maze has one entrance and one exit. For example, if xs represent the walls, a maze could appear as follows: XXXXXXXXXXXXXXXXXX X X X XXXX X X XXXXX XXXXX XX X X XXXXX XXXXXXX XX X X X XX XX X X XXXXXXXXXX XX X XXXXXXXXXXXXoXXXXXXX A creature, indicated in the previous diagram by o, sits just inside the maze at the entrance (bottom row). Assume that the creature can move in only four directions: north, south, east, and west. In the diagram, north is up, south is down, east is to the right, and west is to the left. The problem is to move the creature through the maze from the entrance to the exit (top row), if possible. As the creature moves, it should mark its path. At the conclusion of the trip through the maze, you should see both the correct path and incorrect attempts. Note that some mazes might have more than one successful path, while others have no path. Squares in the maze have one of several states: CLEAR (the square is clear), WALL (the square is blocked and represents part of the wall), PATH (the square lies on the path to the exit), and VISITED (the square was visited, but going that way led to an impasse). This problem uses two ADTs that must interact. The ADT creature represents the creatures current position and contains operations that move the creature. The creature should be able to move north, south, east, and west one square at a time. It should also be able to report its position and mark its trail. The ADT maze represents the maze itself, which is a two-dimensional rectangular arrangement of squares. You could number the rows of squares from the top beginning with zero, and number the columns of squares from the left beginning with zero. You could then use a row number and a column number to uniquely identify any square within the maze. The ADT clearly needs a data structure to represent the maze. It also needs such data as the height and width of the maze given in numbers of squares and the row and column coordinates of both the entrance to and the exit from the maze. The ADT maze should also contain, for example, operations that create a specific maze given descriptive data that we will detail to display a maze, test whether a particular square is part of the wall, see whether a particular square is part of the path, and so on. The input data to represent a maze is simple. For example, the previously given maze is represented by the following lines of input, which can be in a text file: 20 7 width and height of the maze in squares 0 18 row and column coordinates of maze exit 6 12 row and column coordinates of maze entrance XXXXXXXXXXXXXXXXXX X X X XXXX X X XXXXX XXXXX XX X X XXXXX XXXXXXX XX X X X XX XX X X XXXXXXXXXX XX X XXXXXXXXXXXX XXXXXXX After the first three lines of numeric data in the file, each of the next lines corresponds to a row in the maze, and each character in a line corresponds to a column in the maze. An x indicates a blocked square (part of the wall), and a blank indicates a clear square. This notation is convenient because you can see what the maze looks like as you design it. Use a stack-based algorithm to find a path through the maze. The search algorithm and its supporting methods are outside both of the ADTs creature and maze. Thus, the maze and the creature will be arguments that you must pass to these methods. Task: Create a class that represents a maze and recursively finds a path through it OUTPUT looks like this

x File File Edit Selection View Go Run Terminal Help Maze.java - Untitled (Workspace) - Visual Studio Code X EXPLORER > UNTITLED (WORKSPACE) > OUTLINE og JAVA PROJECTS > Ch06_Project01 > Cho5_Project09 > Ch09_Project02 Ch09_Projecto9 Ch09_Project09 & Maze > JRE System Library (jdk-11.0.9.101-h... > Referenced Libraries GDL FR 9 Maze.java x Ch09_Project09 > Maze.java > Maze 1 import java.util."; 2 /** Maze.java 3 A class that represents a maze and recursively finds a path through it. 4 @author Professor Lili Saghaf 5 public class Maze 7 { 8 private static final int EMPTY = 0; private static final int WALL = 1; 10 private static final int VISITED = 2; 11 private static final int PLAYER = 4; 12 private static final int GOAL - 5; 13 14 private int rows; 15 private int columns; 16 private int squares[](); 17 18 private Scanner keyboard = new Scanner(System.in); 19 20 private int startRow = -1, startcol = -1; ES A PROBLEMS 5 OUTPUT DEBUG CONSOLE TERMINAL 4: Java Process Console + X XXXX X XOX X xx XOX XX X X X X ox x x x xx xxxxx xxxxxxxxxxxxx P: play the maze S: get the solution to the maze X: exit D A5 Ln 4, Col 35 Tab Size: 4 UTF-8 LF Java JavaSE-11 OR ENG 12:00 PM