Honors Programming Assignment 1

Computer Science 102

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 pruning.

Finally, after you have sucsessfully generated a path that reaches the exit point, mark the prunned path to the entrance with asterisks,


Samuel Marateck
SUN FEB 10 22:23:14 EST 2008