In this project, you will review basic linked data structures by implementing a stack using a linked list. You will use your stack as part of a maze-solving program.
Most of us know that, were we to find ourselves lost in a simple maze, we will find a way out if we choose a wall, touch it, and move forward always keeping our hand on the wall. This is mostly true; see the following amusing list of ten mazes that can't be solved this way. This is fine if we are in a maze or even if we are solving a maze on paper where we can follow the wall visually, but how would we write a program to solve a maze?
The first question is how to encode a maze. We are going to use a very simple cell-neighbor representation that depends on labeling each of the nn squares of the maze with the labels 0n10n1. Furthermore, we will always assume that the start of the maze is at square 0, and the end is at cell n1n1. As an example, consider the following five-by-five maze. The squares have been labeled 024024; the order of the labeling doesn't really matter, except that the maze is meant to start at the top-left square (so this must be square 0) and to end at the bottom-right square (so this must be square 24).
+--+--+--+--+--+
|0 5 10|15 20|
+ +--+--+ + +
|1 6 11 16|21|
+ +--+--+--+ +
|2 7 |12 17 22|
+--+--+ +--+ +
|3 8 |13|18 23|
+ +--+ + +--+
|4 9 14|19 24|
+--+--+--+--+--+
To encode this maze so that it is easy to read into a program, we will list each square along with its reachable neighbors. For example, from square 0, it is possible to reach squares 1 and 5, so we encode square 0 as the triple (0,1,5). The encoding of the maze in a data file might begin as follows:
0, 1, 5
1, 0, 2, 6
2, 1, 7
3, 8, 4
4, 3, 9
5, 0, 10
etc.
Assume we've read the encoded maze into an array or vector so that we can easily look-up the neighbors of any square. Then it is clear how our program must start: look-up the neighbors of square 0, which are squares 1 and 5, and choose one to move to. Suppose we chose to move to square 5. The next step would be to look-up the neighbors of square 5, which are squares 0 and 10, and choose one to move to. However, we clearly should not return to square 0, as that would leave a portion of the maze unexplored. Going back to a square we have already visited is called backtracking: we should not backtrack unless it is our only option!
How can we prevent backtracking? We must not only keep track of the current square being visited, but also the previous square, and only move back to the previous square if the current square has no other unvisited neighbors.
A stack is a reasonable data structure for storing our progress through the maze. We begin by pushing the starting square (0) onto the stack. Then our solver must read the top element on the stack and see if the square has any neighbors to visit; if so, it chooses a neighbor, pushes it onto the stack, and repeats the process. Thus, the top element on the stack, is always the current square. If the current square has no unvisited neighbors, we backtrack by popping the square off the stack. If the stack is ever empty, there is no solution; if we reach square n1, we have found a path through the maze, and the path can be constructed from the elements on the stack.
Suggestion: It would be a good idea for you to execute this method to completion by hand on the sample maze.
There are a couple bookkeeping details to worry about. When the program backtracks, it must record that the current square is a dead end. One way to do this, is to delete the square from its predecessors list of neighbors.
Returning to the example, we would discover that square 10 is a dead end and would backtrack to square 5 by popping 10 from the stack; to make sure we did not attempt to visit square 10 again, we would remove it from 5's neighbor list, perhaps by overwriting its entry with a flag value:
5, 0, -1
We also need to keep track of the previous square in addition to the current square. So, rather than simply pushing the current square onto the stack, we will push the pair (previous square, current square). But what is the previous square for square 0, the start of the maze? We will again use a flag value (-1) to indicate a vacant predecessor, so the first element pushed onto the stack will be the pair (-1, 0).
The provided .h file defines the constant VACANT to have the value of -1; you should use this constant to indicate deleted or empty neighbors as well as the predecessor to square 0.
You must complete the Maze class by implementing the stack, maze solver, and other miscellaneous functions. You are provided with the following incomplete class files:
The stack class, called SolverStack, is a nested class within Maze. The stack is to be implemented using a linked list with the node structure defined in the provided maze.h file. The solver must use the stack as outlined in the project description to find a solution to the maze, returing the solution (a path, in order, from start to finish) as an integer vector; if there is no solution, it should return an empty vector.
Additionally, you are responsible for thoroughly testing your program. For grading purposes, it will be tested on mazes other than those provided with the assignment. Your submission will also be checked for memory leaks and memory errors.
Here are the specifics of the assignment, including a description for what each member function must accomplish.
Requirement: SolverStack must be implemented as a linked list using the class definition and node structure provided in maze.h. In particular, it must be a nested class within Maze.
Requirement: the STL vector and pair classes are needed in the project, but no other libraries or STL containers may be used.
Requirement: A domain_error exception should be thrown is an attempt is made to pop() or read() an empty SolverStack. A domain_error exception should also be thrown if the solve() function is called on an empty Maze object.
Requirement: you may not make any changes to code provided in maze.h; however, you may add prototypes for private helper functions in the private: section of the Maze class.
Requirement: the implemenation of the maze solver (solve() function in the Maze class) must use SolverStack and the stack-based algorithm outlined in the project description.
Requirement: your code must compile and run with all provided test programs. Additional programs and data will be used for grading.
Requirement: per our course coding standards, your code must compile with g++ on the GL servers without using any compilation flags.
Following are the functions you must implement in the Maze::SolverStack class. Some functions (constructor, test if empty) are provided. See maze.h for prototypes and additional comments.
~SolveStack();
Destructor for the linked list stack implementation. Must delete all the nodes in the list.
void push(src_dest_t src_dest);
The stack push operator. The stack stores elements of type src_dest_t, which is just a source-destination pair (defined in maze.h.)
src_dest_t pop();
The stack pop operator. Must return the src_dest_t value at the top of the stack and remove the item from the stack.
src_dest_t read() const;
Read (return) the src_dest_t value at the top of the stack, but do not remove it from the stack.
Following are the functions you must implement in the Maze class:
~Maze();
The Maze class destructor.
std::vector< int> solve() const;
The maze solving function. It must implement the stack-based algorithm using the SolverStack class. If a solution to the maze is found, the function returns an integer vector containing the path from start to finish in order (beginning with 0 and ending with n1n1). If no solution is found, return an empty vector.