Project 4 Solutions: Maze Generation and Solving
CSE 143
Summer 1998
There are two main ways to attack maze solving: a recursive method and a stack-based
method. Furthermore, after talking to a couple of students, I came across (and
recalled) a novel solution which uses no recursion or dynamic data -- it solves
the maze with a single while loop! I present all three versions here. The only
files that are different between the three versions are bot.h and
bot.cpp (way to go abstraction barriers!) Furthermore, the
stack-based solution needs a stack ADT, which is defined in collections.h
and collections.cpp
It would be a good exercise to read and understand all three maze solving
algorithms, as well as the maze generation algorithm, which is shared by all
three versions of the solution.
The recursive solution:
The stack-based solution:
The iterative solution:
cse143-webmaster@cs.washington.edu