Problem Statement Consider a maze made up of rectangular array of squares, such as the following one: XXXXXXXXXXXXX X XXXX X X X X XX X XX XX X X XX X X XX XXXXX X X XXXXXXXXXXXXX Figure 1--- A sample maze The "X" blocks represent a blocked square and form the walls of the maze. Let us consider mazes that have only one entrance and one exit, as in our example. Beginning at the entrance at the top left side of the maze, find a path to t exit at the bottom right side. You can move only up, down, left, or right. Square is either clear or blocked by an X character. Let a two-dimensional array represent the maze. Use a stack data structure to find a path through the maze. Some mazes might have more than one successful path, while others might have no path. Hints: The primary consideration is that if you reach a dead end, you need to be able to backtrack along the path to the point where you can try a different path. The stack data structure makes it possible to store the current path and backtrack if necessary. Every clear position visited in the current path is pushed to the stack and if a dead end is reached, the previous position is popped from the stack to backtrack. You need to have a loop that begins with the start position and pushes it into the stack then moves to a neighboring cell until either the goal position is reached, or the stack becomes empty. Make sure to mark each clear array cell you move to as visited to avoid checking it again and getting stuck in an infinite loop. For example, each array cell can have three different values: "X" for blocked, "V" for visited, and "*"* for clear. A dead end is an array cell whose all neighbors are either blocked or already visited. What you need to do: There are four files you should pay attention to: Position.java: a class to store the position of an array cell. It has two attributes: row and column along with their accessor and mutator methods. It also has an equal's method that checks for equality of two Position objects. Maze.java: a class to store a maze. It has 3 attributes: a two-dimensional character array which represents the maze, a Position object to represent the start location, and another Position object to represent the stop location. MazeSolver: This class contains one static method, solve. It accepts a maze and returns an array of Positions that is used to traverse the maze if the maze is solvable. If the maze is not solvable then an empty array is returned. o Keep in mind that stacks store objects in reverse order so be sure to return the position array in the correct order. Tester: a sample driver class which calls the traverse method on a maze in either the SolvableMaze, UnsolvableMaze, or HugeSolvableMaze files. These should be at the root of the project folder. You only need to implement the solve method in the MazeSolver.java class. This method receives the maze to solve as a parameter and returns an array of Position objects which stores a solution to the maze if such solution exists; otherwise, it returns an empty array. Note: There might be more than one possible solution to a maze, depending on the ordering in which the neighboring cells are visited at each location. You can do whatever order you want if the maze is solved. For instance, First move left, if the left neighbor is not clear, then move right, if the right neighbor is not clear, then move up, if it is not clear, then move down. You may create any additional helper methods to aid you. For instance, you may make a method to convert the stack to a necessary array. Just remember, when you grab the information from a stack you are getting in the reverse order you push them. You must solve the problem using a Stack. You may use the built-in stack library but use of any other data structure is prohibited apart from constructing the final Position array result. Recursion is also not allowed. What you need to turn in: You need to submit the MazeSolver.java file containing your implementation of the solve method. Rubric Stack is utilized Iterative solution Returns correct solutions to solvable mazes 10 Returns correct solutions to unsolvable mazes 10 Additional Notes and Helpful Hints First hint I have is to not be afraid of creating additional variables to store information. For instance, you must move up, down, left, and right (or north, south, west, and east). Creating Position objects to represent these movements is perfectly acceptable. You will also want to create an object that is the walker of the maze. This walker keeps the current position in the maze. Other than push, pop, and peek on the Stack class, isEmpty is also a useful method. The maze class contains a bunch of methods that is meant to help you. Read what the methods do and decide which ones you want to use for your solution. Read the code given to you FIRST before starting to write your code so you can utilize it. It is there to make your life easier, not harder. Try to translate what you want to do in terms of the stack operations. For instance, if you find yourself at a dead end then you want to move back to a previous position. This means you will need to first pop the top position, which contains the spot located at the dead end, then peek to see where you need to be. Your stack should be declared and initialized as such: Stack Give it a name new Stack (); where you can name it whatever you want. Moving in a two-dimensional array requires the following math: Move up (North) Row+ I Move down (South) Row - I Move left (West) Move right (East) Column-1 Column + 1 HUGE UNSOLVABLE MAZE 101 0 0 100 99 XXXXXXX XXXXX X X X X X X X X X X X X X X X X X XXX X XXX XXX X X XXXXXXX X XXX XXXXXXXXXXX XXXXXXXXXXXXX X XXXXXXXXX X X X X XXXXX X XXX X X X X XXX X X X X X X X XXXXXXXXX XXX XXX X XXX XXXXXXX X XXXXXXX x X Page 1 of 4 3 XXXX X X X X X X X X X XXX XXXX 2600 words X3X3 X X X X X X X XXX XXXXX XXX X X X XXX XXX X X XXX XXXX XXXXX XXX xxx x x X X X X X X X X X X X X x3 XXXXXXXXXXXX XXX X3 X X X X3 X X X X X XXX X XXXXX XXXXX X X XXXXXXX X X X XXX XXX X XXX X XXX X XXX XXX x3 X X X X x X X X XXX X X I X X X X x x XXXXXXX XXXXXXXXXX X X X X x3 X X X X X X X X SOLVABLE MAZE 21 0 0 19 20 XXXXXXXXX (XXXXXXXXX X X X X SAA VA X XXXXX X X XXXXX X X X X X X X X X XXX XXXXXXXXXXXX X X X X XXXXX XXX XXXX X X X X www. X X X KXXXX XXX X XXX XXX X X X X XX X X X X X XXXXXXX. XXXXXXX XX X X X X XXXXX XXX X X XXX X X X X XX UNSOLVABLE MAZE 21 0 0 19 20 . XXXXXX X X X XXXXX X X XXXXX XXX X X X X XX X X XXXXX X XXX XXX X X X XX XXX X XXXXXXXXXX X . X X X X X X X X X X X X X X X X X X XXX X XX X X X X X X X . X XXX ' X X X XXXXXX X