CS 70

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:

  1. 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).
  2. 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).
  • LHS Cow speaking

    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.

  • Hedgehog speaking

    Recursion freaks me out.

  • LHS Cow speaking

    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!

  • Horse speaking

    Hay! So CoordVector is basically a stack?

  • LHS Cow speaking

    Exactly! With pushBack() and popBack(), 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:

  1. Start at the maze entrance.
  2. Mark our current position as ACTIVE (we're building a path).
  3. Look for unexplored neighbors (PATH cells).
  4. If we find unexplored neighbors, pick one and move there.
  5. If we hit a dead end, backtrack by marking dead-end cells as VISITED.
  6. 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.

  1. The first pop explores from that cell.
  2. 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 it VISITED, 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
  • Cat speaking

    Why do we push the current cell back onto the stack after marking it ACTIVE?

  • LHS Cow speaking

    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 as VISITED instead.

  • Duck speaking

    So ACTIVE cells are like breadcrumbs showing our current path?

  • LHS Cow speaking

    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 returns false for all states.
  • 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
  • Duck speaking

    Mine just crashed immediately!!

  • LHS Cow speaking

    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!
  • Hedgehog speaking

    It crashed with CoordVector is full!

  • LHS Cow speaking

    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:

  1. PATHACTIVE: When we first explore it.
  2. ACTIVEVISITED: When we backtrack from a dead end.
  3. 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).
  • Hedgehog speaking

    I got it working easily enough (phew!), but my understanding of why it works is still fuzzy.

  • LHS Cow speaking

    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.

  • RHS Cow speaking

    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.

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)