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).

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.

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:

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

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-7x7.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-21x7.txt         # Animated solve
./amaze -n mazes/maze-21x7.txt      # Instant solve

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!

(When logged in, completion status appears here.)