Solving the Maze, Part 1
We're now ready to start working on the maze-solving part of the assignment.
For problems like this one, there are two possible approaches:
- Depth first – try one path as far as it goes, back up if you hit a dead end, and try another path. This approach is sometimes called a “backtracking” approach, or depth-first search (DFS).
- Breadth first – explore all possible paths one step at a time, until you find the exit. This approach is sometimes called breadth-first search (BFS).
These approaches are applicable to a broad range of problems, not just mazes! For example, they can be used to find paths in graphs, or to solve puzzles like Sudoku.
In this part, we're going to implement a depth-first search. Later on, we'll implement breadth-first search as well.
The Depth-First Search Approach
The depth-first algorithm involves following a path and then backing up when we hit a dead end. In that sense, it matches up well with the idea of a stack data structure, where we can add new items to the top of the stack and remove items from the top of the stack. (This is sometimes called a LIFO, or Last In First Out, data structure.)
One common approach is to use recursion, where the function calls itself to explore a new path. Each time the function is called, a new stack frame is created on the call stack, which holds the local variables for that invocation of the function. When the function returns, that stack frame is popped off the call stack.
Recursion freaks me out.
Well, you're in luck, because we're going to avoid recursion in this assignment. Instead, we're going to manage our own stack explicitly using the
CoordVector
you just built!Hay! So
CoordVector
is basically a stack?Exactly! With
pushBack()
andpopBack()
, it works perfectly as a stack. (The back of the vector is the top of the stack.)
Understanding the Algorithm
Before we dive into code, let's understand how DFS works for mazes. The key insight is that we'll use the maze itself to track our progress:
Maze::PATH | |
An unexplored open path. |
Maze::ACTIVE | o |
Part of our current solution path. |
Maze::VISITED | . |
Explored but not part of the solution. |
Here's how the algorithm works conceptually:
- Start at the maze entrance.
- Mark our current position as
ACTIVE
(we're building a path). - Look for unexplored neighbors (
PATH
cells). - If we find unexplored neighbors, pick one and move there.
- If we hit a dead end, backtrack by marking dead-end cells as
VISITED
. - Repeat until we find the exit or run out of places to explore.
The Clever Trick: Double-Pushing
Our implementation uses a neat trick to handle backtracking—each cell is pushed onto the stack and popped off twice.
- The first pop explores from that cell.
- The second pop (if we come back to it) cleans up by marking it as
VISITED
.
We use the state of the cell in the maze to know which pop we're doing:
- If the cell is
PATH
, it's the first pop (explore it). - If the cell is
ACTIVE
, we'd been trying to build a path from this cell, but it didn't lead to a solution, so now we mark itVISITED
, abandoning that path.
This approach elegantly handles the backtracking without needing extra data structures!
The Algorithm in Detail
SOLVE-MAZE-DFS(maze): create empty stack push start coordinate onto stack while stack is not empty: current = pop from stack // Handle cleanup for backtracking if current is ACTIVE: mark current as VISITED // Dead end, not part of solution continue to next iteration if current is VISITED: // skip this cell—already explored continue to next iteration // This cell is part of our current path mark current as ACTIVE push current onto stack // Push again for potential cleanup if current is the end: return true // Found the solution! // Add all unvisited neighbors to explore for each direction in (up, down, left, right): neighbor = current + direction if neighbor is PATH: push neighbor onto stack return false // No solution found
Why do we push the current cell back onto the stack after marking it
ACTIVE
?If this path leads to the exit, we'll never pop it again—the
ACTIVE
cells form our solution. But if it's a dead end, we'll come back to it later and need to mark it asVISITED
instead.So
ACTIVE
cells are like breadcrumbs showing our current path?Exactly! And when we backtrack, we change them to
VISITED
to show “been there, didn't work”.
Your Task: Implement solveMazeDFS
Step 1: Set Up the Function
Open solver.cpp
and find the solveMazeDFS
function. You'll see it currently makes a half-hearted attempt to solve the maze and returns false
. You can delete that code.
Start with the basic structure:
bool solveMazeDFS(Maze& maze) {
CoordVector toDoStack;
toDoStack.pushBack(maze.getStart());
Coord end = maze.getEnd();
// Main loop goes here
return false; // If we exit the loop without finding the end
}
Step 2: Implement the Main Loop
Follow the pseudocode above to implement the main loop.
Remember:
- Use
maze.hasState(coord, state)
to check a cell's current state.- Conveniently, if you give out-of-bounds coordinates,
maze.hasState
just returnsfalse
for all states.
- Conveniently, if you give out-of-bounds coordinates,
- Use
maze.setState(coord, state)
to change a cell's state. - The
DIRECTIONS
array is already defined for you—use it in your loop.
Step 3: Test Your Implementation
Compile and test with a small maze first:
make
./amaze mazes/maze-07x07.txt
You should see the maze solve itself! The ACTIVE
cells (o
) show the solution path.
You can solve both with and without animation:
./amaze mazes/maze-21x07.txt # Animated solve
./amaze -n mazes/maze-21x07.txt # Instant solve
Mine just crashed immediately!!
Check out the helpful hints below for debugging tips!
Step 4: Test with Larger Mazes
Once your solver works on small mazes, try progressively larger ones:
mazes/maze-51x11.txt
— Should work fine.mazes/maze-79x23.txt
— Might work…mazes/maze-91x43.txt
— Uh oh!
It crashed with
CoordVector is full
!Exactly! Our
CoordVector
can only hold 256 coordinates, but complex mazes need more stack space. We'll fix that limitation in the next part!
Helpful Hints
Understanding State Transitions
A cell goes through these states:
- PATH → ACTIVE: When we first explore it.
- ACTIVE → VISITED: When we backtrack from a dead end.
- Stays ACTIVE: If it's part of the final solution path.
Debugging Tips
- Use the status line! Call
maze.showStatusText("Exploring: " + current.to_string())
to track progress. - Run with
-n
flag for instant solving when debugging logic. - Run without
-n
to watch the algorithm work step-by-step. - Start with the smallest maze (
maze-07x07.txt
) first.
Common Mistakes
- Not following the provided pseudocode closely (e.g., trying a different approach that you think would be “more efficient”).
- Forgetting to push the current cell back onto the stack after marking it
ACTIVE
. - Not checking all four directions for neighbors.
- Confusing the order of operations (mark
ACTIVE
, then push, then check for end).
I got it working easily enough (phew!), but my understanding of why it works is still fuzzy.
Watching the algorithm go step-by-step with animation can really help solidify your understanding. You can see how the stack evolves and how cells change state as the algorithm explores and backtracks. You can add status messages to the maze display to track what the algorithm is doing at each step, or use the
.setPause(milliseconds)
function to slow it down even more.But you'll see DFS over and over in different contexts, so the understanding will come with practice. The not-so-secret real purpose of this assignment is to learn about how data structures like
CoordVector
work, not to ponder all the ways that depth-first search can be implemented.
(When logged in, completion status appears here.)