Spring 2008 Generating a random maze and solving it by recursive back-tracking
Introduction
You are required to generate a maze consisting of a 12 by 12 grid where
the borders (row 0 and 11, and column 0 and 11) are walls. The walls within
the grid should be generated randomly, for example:
Maze before traversal | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
The entrance to the maze will be the first gap in column 1 (here it is in row
2) and the exit of the maze will be the first gap in column 10 that the
path reaches (here it's in
row 1 and indicated by a #). As your program traverses the maze, in should
place consecutive integers in each cell on the path to the exit starting with 1
in the entrance as shown here:
Maze after traversal | | | | | | | | | | | | | | 2 | 5 | 8 910 | # | | 1 3 4 6 7 | |11 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Another randomly generated maze and its solution (for the recursive
call sequence NW, N, NE, W, E, SW, S, SE) is:
Maze after traversal | | | | | | | | | | | | | | 3 4 | 7 8 91011 | | | | 2 5 615 |131218 | | | 1 | | |141617 | | | | | | |21201922 | # | | | | | | | |2324 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Press any key to continue...
The Assignment
Draft #1
Write your program so that it displays the maze before the traversal, calls a
recursive method to traverse the maze and prints the maze after the traversal
is compleat. If there is no possible path between the entrance to the maze and
the exit, or if there is no entrance or exit please indicate this by throwing
an exception.
Notice that the path indicated by cells 7, 8, 9, 13, 14,
15, 7 forms a loop. In order to prevent unnecessary moves or an infinite loop,
either use a 2-dimensional array of boolean called visited to record
whether or not a cell was visited; or use another test. Note that a legal move
can be one of eight directions: NW, N, NE, E, SE, S, SW, W, assuming that there
is no wall to prevent the move. The figure above shows back-tracking when for
instance, the traversal goes from cell 14 to 15. Since 15 is dead end, the
execution back-tracks to cell 14. This is done automatically by the JVM when
it pops the run-time stack.
The same maze as the one above; but the recursion going clockwise from
NW, N, NE, etc.
----------------------------- | | | | | | | | | | | | | | 3 4 | 6 7 8 910 | | | | 2 5 |131411 | | | 1 | | | 1512 | | | | | | | 16 | # | | | | | | | | 17 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |Draft #2
The path through the maze can be represented by a
graph. (A graph whithout any loops is called a tree.) The unsuccessful side
excursions are indicated by branches (cells 17 and 18 form a branch). The
process of removing branches from a tree is called
Finally, after you have sucsessfully generated a path that reaches the
exit point, mark the prunned path to the entrance with asterisks,