Class Diagram:
See image. Class diagram.
Assignment #11 will be the construction of a program that solves a maze problem.
Your program needs to find a way to go from the upper right corner (where you see '>' character) to the lower left corner (where you see '<' character). If you see a dot '.', that mean that slot is available to go through, but if you see a pound sign '#', that means that there is an obstacle and you cannot go through there.
Whenever you go though, you need to change the character at that position to '.' to 'x'. It is possible that one path that you try might lead to a dead end. In that case, you need to backtrack to try another path. The position you decide not to include in your solution path should now be changed to 'O' to record that you have already tried that position. Therefore in this assignment, you will store a successful path (a sequence of positions) in a stack. Whenever you proceed to a new position, you need to push that position information onto the stack. When you decide to back track, you need to pop the position that you are not using as part of a solution path.
In this way, when you reach the goal, the stack should contain a sequence of positions that you took from the starting point to the goal. Also, if one sees the result maze, he/she can also track the solution path by following Xs that you recorded in the maze.
Here is an example. Suppose that you are given the following maze:
.........>
#....#...#
#....##..#
....#.##..
#..#......
.###.#..#.
..#.##....
#....#.##.
.##..#.###
<.#.###...
Then a solution is:
.........>
#....#..x#
#....##.x#
....#.##x.
#..#.x..x.
.###x#xx#.
..#x##xx..
#xxxO#x##.
x##xO#O###
<.#O###OOO
The sequence of Xs shows the solution path. Note that the positions with an O are already visited, but reached a dead end, so it was removed from the solution path.
You will be given a maze with the size of 10 rows and 10 columns. You need to start from the upper right corner (row = 0, column = 9), and check which adjacent position is available (not '#' or 'O' or out of bounds). When you do this checking, you MUST check in the following order:
This class pairs a row number (int) and a column number (int). Its constructor takes a row number and a column number, and it has accessor methods for row and column, getRow() and getColumn().
It also has a face which keeps track of which direction to go from that position so that it can show a solution at the end. It has an accessor method and a mutator method of face and also toString method.
Face values of 0,1,2,3,4,5,6, and 7 represent the direction of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right' respectively.
This class is given by the instructor.
This class displays a menu for the Maze Problem. If a user enters "E", then it asks to enter an initial maze configuration, then it will display a result for the problem. This class is given by the instructor.
The MazeSolver class contains a constructor to set up an initial maze configuration.
It also contains methods to print out a result maze as well as a solution path. These methods are given by the instructor.
You need to complete the following findSolution method based on its pseudo-code.
You need to write the findSolution method that determines whether there is a solution to the Maze problem. It should return true if a solution is found, false otherwise. If a solution is found, then the program should display the result maze with Xs and Ox. Your program should display intermediate steps by printing "Trying the position of row 2 and column 7".
Each time a choice is made, the choice is pushed onto a stack that already contains all the previously made choices. The following is the pseudo-code for this. It assumes that for a 10-by-10 maze, rows vary from 0 to 9 and columns vary from 0 to 9. You need to start with (0,9), then try to find an adjacent position to move to. (In this case, trying to go to (1,9).If this does not work, then you need to try to go to (1,8), etc.
boolean success = false;
boolean finish = false;
Push (0,9) -- row 0 and column 9 information onto the stack indicating the first choice is (0,9).
while (finish = = false && stackSoln.isEmpty( ) = = false)
{
Check the most recent position from the stack, and check which of eight adjacent positions to move from the recent position,
in the order of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right'.
This part requires another nested loop to repeat at most 8 times to check eight adjacent positions.
If such adjacent position is not outside of the maze range,
row and column being greater than or equals to 0 or less than or equals to 9, and being able to move into
(it needs to contain 'x' or '<' the goal position),
then we found a position to move to.
As soon as we find a position to move to, save its direction to 'face' variable and get out of the loop
('face' can contain 0,1,2,3,4,5,6, and 7 representing the direction of
'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right' respectively).
If the found adjacent position to move to is the goal position (contains '<'),
then we found a solution path, and set 'success' to true and 'finish' to true.
Also set the face of the current position to 'face' value obtained by the above loop.
If the found adjacent position to move to is not the goal position,
then push the object of such adjacent position onto the stack, and set the adjacent position to 'x'.
Also set the face of the current position to 'face' value obtained by the above loop.
If we cannot find any adjacent position to move to, then set the current position to 'O', if it was 'x'.
Then pop the solution stack, which means not including this position in the solution path.
If the stack is empty at this time, then there is no other place to back track, thus the maze does not have a solution.
Set 'success' to false and 'finish' to true.
} //end of while loop
return success;
You need to implement this method using an object of the Stack class in java.util package. This stack will contain objects of the Position class.