18 20_MazeTraversal_Hard
The gird of #'s and dots (.) in figure below are a two-dimensional array representation of a maze. The #s represent the walls of the maze, and the dots represent locations in the possible paths through the maze. A move can be made only to a location in the array that contains a dot. Write a recursive method mazeTraversal to walk through mazes like the one in figure below. The method should receive as arguments a 12-by-12 character array representing the maze and the current loaction in the maze (the first time this method is called, the current location should be the entry point of the maze.) As mazeTraversal attempts to locate the exit, it should place the character x in each sqaure in the path. Program the method to display the maze after each move so the user can watch as the maze is solved. The final output of the maze should display only the path needed to solve the maze--if going in a particular direction results in a dead end, the x's going in that direction should not be displayed.
To start the and view how the maze is solved, compile and run MazeTraversal. The maze will automatically be loaded and start to be solved. The maze will be updated in real time as it is being solved. If a solution is found then you will be notified and the final solution will be showed. If there is no solution then you will be told so.
MazeSolver can solve any two dimensional maze given that it can defined by a single type of wall and single type of path. MazeSolver is constructed with information about the maze and once mazeTraversal is called the maze will start to be recursively solved. The initial row and column passed will be the starting point of the maze. The recursion starts by checking if the maze is already solved. If it isn't solved it attempts to move up, then right, then down and finally left. If it can move in one of the directions it immediately will. A direction is moveable only if the destination it's moving to is the moveChar. If there are no valid new directions, it will then try to move moveChar instead in the up, right, down and left in order. If any of those are successful it will immediately move backwards in that direction. If neither of those options of mazePath or movePath are available in any directions the function will return false since the maze is unsolveable.
The tryMoveTo method checks if a position is valid by checking canMoveTo which aggressively checks if the given row and col is equal to the given char. If an ArrayIndexOutOfBoundsException is thrown then the method will return false.
MazeTraversal gives an example maze and parameters shown to solve the maze. You can easily change to values passed to the MazeSolver to better solve your 2D maze.
UML Diagram:
The java documents are served from a local web server on this machine. To start the web server, navigate to the directory immediately above where the source code is checked out (i.e. ~/git ) and then use "python -m SimpleHTTPServer" in that directory.
cd ~/git
python -m SimpleHTTPServer&Note: if you are running python 3 (which you can check via opening a terminal and typing: python --version), then the command is:
python3 -m http.server