# Traverse the Maze

Objective
This project provides experience of implementing recursive methods and using a generic linked
stack data structure for the purpose of an efficient depth-first search for the longest path in a
special tree structure. You will also review how to construct and use Java classes as well as
obtain experience with software design and testing.
ABET Program Learning Outcomes:
The ability to recognize the need for data structures and choose the appropriate
data structure (1,2,6)
The ability to implement and use stacks (1,2,6)
The ability to implement and use linked list and array based structures (1,2,6)
The Problem
The programming problem in this project is to find a path from the entry cell (upper left corner)
to the exit cell (lower right corner) of a maze. In our model the rectangular maze is represented
by a grid of cells. Each cell is bordered by 4 walls, and some of these walls are passable to the
neighboring cell(s). The outside wall of the whole maze is not passable. There are however (at
least) two very different interpretations of a passable wall. We say that the maze is directed if
for any given pair of cells A and B there are four cases:
– there is no passage between A and B
– each of A or B is accessible from the other
– B is accessible from A, but A is not accessible from B
– A is accessible from B, but B is not accessible from A
On the other hand, in an undirected maze each passage provides a two-way access, that is, there
are only two cases, #1 and #2 as listed above.
In this project your program shall exercise both options of building a maze, moreover in the
directed maze every passage will be selected by a given probability, while the undirected maze
will be built upon a pattern of predetermined passable walls. Your completed program is able to
build a maze based upon input wall pattern read from a file
build a maze with a random selection of all relevant directional passage
find a path through a maze if such a path exists
display the maze solution on the console showing the length of the path and the
locations of the cells along the path from the entry cell to the exit cell
report the failure of the search in an output message