Written in JAVA

In this lab you will write a program that simulates a mouse in a maze. The maze will have one exit location. The mouse will start from some location in the maze and move to different locations until it gets out of the maze or gets stuck. (Your mouse will be smart enough to know that it is stuck, as long as it doesn't follow a path that contains a loop!) Sometimes the mouse will come to a dead end and will need to backtrack to try another path. No matter where the mouse is in the maze, the mouse can only travel in one of the four cardinal directions, north (up), south(down), east(right) and west(left):

The program must print the path taken by the mouse from the starting location to the final location, including all locations that have been visited and all locations through which it has backtracked.

A two dimensional array can be used to store the maze. Each element of the array will be a location, which can be in a passage or in a wall. The mouse can be in a passage but not in a wall. In the array, represent a passage location by a ' ' (space) and represent a wall location by an 'X' (letter X). Here is a sample maze (your maze will be larger):

 XXXXXX XXXX X XXXX X X X XX X X XX X XXXXXX

At each moment of the mouse's journey, it is in some location in the maze. The mouse also remembers the previous location it was in. A location is represented by its array coordinates.

Input

1. read the input file name from the keyboard
2. read the maze from the file and store it in an array; make your maze 15 by 15
3. read the exit location from the file
4. prompt the user and read the starting location from the keyboard

Output

1. print the maze and exit location
2. print each location that the mouse moves into
3. when the mouse backtracks, print each location that it backtracks into, with "**" in front of the location, so it's obvious that the mouse is backtracking
4. if the mouse cannot get out of the maze, print a message saying so
5. if the mouse gets out of the maze, print a message saying so

Processing

Create a Scanner for the keyboard and read in the file name, then read the maze and the exit location from the file. Prompt the user for the starting location, create a mouse in that location, and then search the maze. Use exception handling to ensure the starting location is a valid location. To be valid, the location must be inside the maze and also in a passage, not in a wall. If it's invalid keep the user in a loop until a valid location is provided. After the search finishes, prompt for another starting location and search again. Continue until the user wants to quit.

The search moves the mouse from one location to another in the maze. As the mouse moves, each location it visits is printed. When the mouse enters a location, the search function determines the type of the location. The location type is one of the following:

• Continuing: A location is a continuing location if one and only one of the neighbors (excluding the previous location) is in a passage. In a continuing location, the mouse has only one choice for the next move.
• Intersection: A location is an intersection location if two or more of the neighbors (excluding the previous location) are in a passage. In an intersection location, the mouse has two or three choices for the next move.
• Dead End: A location is a dead end if none of the neighbors (excluding the previous location) is in a passage. In a dead end location, the mouse cannot go forward. It must backtrack.
• Exit: A location is an exit location if the mouse can get out of the maze from that location. When the mouse finds an exit location, it is free, and gets a piece of cheese as a reward. The search is over.

To implement the search, you need two stacks. The first stack, the visited stack, contains the path the mouse is following. Whenever the mouse moves to a new location, it first checks to see if it is an exit location. If not, the location is pushed into the visited stack. This stack is used if the mouse hits a dead end and must backtrack.

When the mouse enters an intersection, a special decision token is pushed into the second stack, the choices stack, and then the possible next moves are pushed into the choices stack. The intersection point is also marked by placing a decision token in the visited stack after the intersection location has been pushed onto visited. The decision token has coordinates (-1,-1). To choose the next move, a location is popped from the choices stack, and the mouse continues to that location.

If the mouse hits a dead end, it must backtrack by popping locations from the visited stack and moving to these locations. Each backtracked location should be printed with a '**' to indicate that the mouse is backtracking.

While backtracking, if the mouse pops a decision token, then the mouse has backtracked to an intersection. Pop one more location from visited and move back to that location. This is the intersection. The mouse is now back at the intersection. Then pop an alternative from the choices stack and the mouse continues forward to that location. Before moving forward, push the intersection location and then the decision token back into the visited stack in case the mouse comes back to this location again later and needs to make another choice. However, if the token popped from the choices stack is also a decision token, then all choices for this intersection have already been tried and the mouse needs to backtrack again until it reaches another intersection. If the mouse is backtracking and it finds that the visited stack is empty, the mouse is trapped in a part of the maze that has no exit. If so, the search ends and the program prints a message saying that the mouse is trapped.

For example, suppose you have the following small maze where the mouse is in (4,1) and the previous location of the mouse is (5,1).

XXXXXXX X XXXXX X XXXXX X XXX X XXXXX X XXXXX XXXXXXX

Since (4,1) is a continuing location, the mouse will move to (3,1). This is an intersection. The possible next moves are (2,1) and (3,2). It's possible for the mouse to move to (4,1), but since that's the previous location of the mouse, we only want to move there if we need to backtrack.

At this point, we need to keep track of the possible next moves, choose one, and also make sure that when we backtrack we know when we've returned to the intersection so we can try another path. Right now the visited stack contains (5,1), (4,1) and (3,1). We push (-1,-1) onto the visited stack so we know we are in an intersection. We push (-1,-1), (2,1), and (3,2) onto the choices stack. The order of (2,1) and (3,2) don't matter; a different order will mean a different path will be searched first, but if that path is a dead end the mouse will come back and try the other path.

Now we are ready to move forward. We pop one location from the choices stack and the mouse continues from that location. So in our example, we pop (3,2) from choices, move the mouse to that location, push it onto the visited stack and print it. Now the visited stack has (5,1), (4,1), (3,1), (-1,-1) and (3,2). The choices stack has (-1,-1) and (2,1). The mouse continues moving forward to (3,3), so the visited stack contains (5,1), (4,1), (3,1), (-1,-1), (3,2) and (3,3). But (3,3) is a dead end, so we have to backtrack. We pop locations from the visited stack and move the mouse back to each of those locations. When we pop the decision token, we have gotten back to the intersection. We pop one more location (the intersection) and move the mouse to that location. In our example, we pop (3,2), move to (3,2), then we pop the decision token. When we pop the decision token we pop one more location from the visited stack; this is the intersection, so we move back to (3,1). Then we pop one location from the choices stack and we get (2,1). This is the other path we can try, so we move to (2,1). The choices stack now has only (-1,-1), meaning there are no more options to try if we end up backtracking back to the intersection. To move to (2,1) we push the intersection back onto the visited stack, since that's where the mouse is now, then we push a decision token onto visited (so we will know that we came from an intersection), then we push (2,1) onto visited. So now our visited stack contains (5,1), (4,1), (3,1), (-1,-1) and (2,1). We move forward to (1,1), so now the visited stack contains (5,1), (4,1), (3,1), (-1,-1), (2,1) and (1,1). (1,1) is a dead end so again we pop locations from visited and move to these locations, until we pop the decision token. Then we pop once more to get the intersection, and move back to the intersection. When we pop the choices stack we get the decision token; this means there are no more choices so we have to continue to backtrack by popping locations from the visited stack and moving back to those locations. After we pop (5,1) the visited stack is empty, so we report that the mouse cannot get out of the maze. This gives us the path:

 (5,1) (4,1) (3,1) (3,2) (3,3) ** (3,2) ** (3,1) (2,1) (1,1) ** (2,1) ** (3,1) ** (4,1) ** (5,1) Dead end, cannot get out of the maze.

To write this program, you will need to design and write three classes.

• The Location class is used to represent a location in the maze. It will have fields for the row and column of the location. Location will be the type of object contained in the visited stack and the choices stack. Location will have many small methods, such as toString, equals, testing to see if a Location contains (-1,-1) (a decision token), setting a Location, and comparing Locations. You may want to write four functions to return the Location above, below, to the right, and to the left of the this. These functions can be used by the function that needs to determine whether a Location in the maze is a dead end, a continuting location, or an intersection.
• The Mouse class will be used to represent the mouse. Mouse will have fields for the current location of the mouse and the previous location of the mouse. It will have a method to move the mouse to a new location (the new location is the parm), and to return the current and previous locations.
• The Maze class has a field to hold the maze (a 15x15 2D array) and a field for the exit location. It has methods to read the maze from a file, print the maze, and search the maze. The parm for search is the mouse; the starting location of the search is the current location of the mouse when the search begins. To read in the maze, read in each line of the file into one row of the maze array. After reading in the maze then read the row and column of the exit location of the maze. These should be on the line after the last line of the maze. The search is a complicated function; DO NOT write one huge search function. Create some private methods that search will call.

Built-in Java classes may be used. The Java vector class may not be used for this assignment. In addition, you must follow all directions precisely as stated.