Rat in a Maze Problem: Stack and Queue Implementation in C++

Introduction to the Rat in a Maze Problem

The Rat in a Maze problem is a classic computational problem that challenges you to find a path from the start to the exit in a grid. In this tutorial, you will implement solutions using stacks and queues in C++, reinforcing concepts from CS3530 lectures 12-14. We'll also cover makefiles, abstract data types (ADTs), and separate compilation — essential skills for any C++ developer.

Why Stacks and Queues?

Stacks (LIFO) and queues (FIFO) are perfect for pathfinding. A stack implements depth-first search (DFS), while a queue implements breadth-first search (BFS). Think of a stack like a browser's back button — you backtrack to the previous page. A queue works like a line at a gaming tournament: first come, first served. In AI pathfinding, BFS finds the shortest path, and DFS explores deep paths quickly.

Setting Up Your Project with Makefiles

We'll use a makefile to compile multiple source files. This is crucial for large projects. Here's a sample makefile:

# Makefile for Rat in a Maze
CXX = g++
CXXFLAGS = -std=c++11 -Wall

all: ratMaze

ratMaze: main.o maze.o stack.o queue.o
	$(CXX) $(CXXFLAGS) -o ratMaze main.o maze.o stack.o queue.o

main.o: main.cpp maze.h
	$(CXX) $(CXXFLAGS) -c main.cpp

maze.o: maze.cpp maze.h
	$(CXX) $(CXXFLAGS) -c maze.cpp

stack.o: stack.cpp stack.h
	$(CXX) $(CXXFLAGS) -c stack.cpp

queue.o: queue.cpp queue.h
	$(CXX) $(CXXFLAGS) -c queue.cpp

clean:
	rm -f *.o ratMaze

This makefile ensures that only changed files are recompiled, saving time — just like incremental updates in a mobile app.

Abstract Data Types and Header Files

We'll define ADTs for stack and queue using header files. Separate compilation means each class is in its own file. For example:

// stack.h
#ifndef STACK_H
#define STACK_H

class Stack {
private:
    int* arr;
    int top;
    int capacity;
public:
    Stack(int size);
    ~Stack();
    void push(int x);
    int pop();
    bool isEmpty();
};

#endif

Similarly for queue.h. This modularity is like having separate components in a gaming engine — each part can be developed and tested independently.

Implementing the Maze Class

The maze is a 2D grid. We'll store it in a file and read it. Example maze.txt:

Where 1 = open cell, 0 = blocked. Start at (0,0), exit at (4,4). The maze class will have methods to load, print, and check valid moves.

Solving with a Stack (DFS)

DFS uses a stack. Algorithm:

Push start cell onto stack.
While stack not empty: pop cell, mark visited, check if exit. If not, push all unvisited neighbors.
If exit found, reconstruct path.

Here's the stack-based solver:

bool solveWithStack(Maze& maze, Stack& path) {
    int startX = 0, startY = 0;
    int endX = maze.getRows()-1, endY = maze.getCols()-1;
    Stack stack(maze.getRows()*maze.getCols());
    stack.push(startX * maze.getCols() + startY);
    bool** visited = new bool*[maze.getRows()];
    for (int i = 0; i < maze.getRows(); i++) {
        visited[i] = new bool[maze.getCols()]();
    }
    visited[startX][startY] = true;
    while (!stack.isEmpty()) {
        int cell = stack.pop();
        int x = cell / maze.getCols();
        int y = cell % maze.getCols();
        if (x == endX && y == endY) {
            // reconstruct path
            return true;
        }
        // check neighbors (up, down, left, right)
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < maze.getRows() && ny >= 0 && ny < maze.getCols() &&
                maze.getCell(nx, ny) == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                stack.push(nx * maze.getCols() + ny);
            }
        }
    }
    return false;
}

DFS is like exploring a dungeon in a game — you go deep until you hit a dead end, then backtrack. It's memory-efficient but may not find the shortest path.

Solving with a Queue (BFS)

BFS uses a queue and guarantees the shortest path. Algorithm:

Enqueue start cell.
While queue not empty: dequeue cell, mark visited, check exit. Enqueue all unvisited neighbors.
Track parent for path reconstruction.

bool solveWithQueue(Maze& maze, Queue& path) {
    int startX = 0, startY = 0;
    int endX = maze.getRows()-1, endY = maze.getCols()-1;
    Queue queue(maze.getRows()*maze.getCols());
    queue.enqueue(startX * maze.getCols() + startY);
    bool** visited = new bool*[maze.getRows()];
    int** parent = new int*[maze.getRows()];
    for (int i = 0; i < maze.getRows(); i++) {
        visited[i] = new bool[maze.getCols()]();
        parent[i] = new int[maze.getCols()];
        for (int j = 0; j < maze.getCols(); j++) parent[i][j] = -1;
    }
    visited[startX][startY] = true;
    while (!queue.isEmpty()) {
        int cell = queue.dequeue();
        int x = cell / maze.getCols();
        int y = cell % maze.getCols();
        if (x == endX && y == endY) {
            // reconstruct path using parent
            return true;
        }
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < maze.getRows() && ny >= 0 && ny < maze.getCols() &&
                maze.getCell(nx, ny) == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                parent[nx][ny] = cell;
                queue.enqueue(nx * maze.getCols() + ny);
            }
        }
    }
    return false;
}

BFS is like a flood fill in a graphics app or the way AI explores a game map level by level. It's optimal but uses more memory.

Comparing Stack vs Queue Solutions

In our maze, DFS might find a path quickly but not the shortest. BFS always finds the shortest path. For a 5x5 maze, both work, but for larger mazes, choose based on needs. In AI pathfinding for a self-driving car, BFS is safer; for a game where exploration is key, DFS is fine.

Compiling and Running

Use the makefile to compile. Run: ./ratMaze maze.txt. The program should output the path found by both methods. Example output:

DFS Path: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3) -> (3,3) -> (4,3) -> (4,4)
BFS Path: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (3,4) -> (4,4)

Real-World Connections

This problem mirrors how AI agents navigate in games like Minecraft or Pokémon Go. In finance, BFS can model shortest payment routes. In social media, it finds friend connections. The stack and queue ADTs are building blocks for more complex algorithms.

Conclusion

You've implemented the Rat in a Maze using stacks and queues in C++, with proper makefiles and separate compilation. This reinforces ADTs, header files, and the power of LIFO/FIFO structures. Practice by adding diagonal moves or weighted cells. Happy coding!