Rat in a Maze Problem in DSA C

Mental Model

Find a path from start to end in a grid by moving step-by-step through allowed cells.

Analogy: Imagine a rat trying to find cheese in a maze by walking only through open paths and avoiding walls.

Maze grid:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

1 = open path, 0 = wall
Start at top-left (0,0), goal at bottom-right (3,3)

Dry Run Walkthrough

Input: maze: 4x4 grid with 1=open path, 0=wall Start: (0,0), Goal: (3,3)

Goal: Find one path from start to goal moving only right or down through open cells

Step 1: Start at (0,0), mark as part of path

Path matrix:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Why: We begin from the start cell which is open

Step 2: Move right to (0,1) - blocked (0), backtrack

Path matrix unchanged:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Why: Cannot move right due to wall, so try other directions

Step 3: Move down to (1,0), mark as part of path

Path matrix:
1 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0

Why: Down cell is open, so continue path there

Step 4: Move right to (1,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 0 0 0
0 0 0 0

Why: Right cell is open, continue path

Step 5: Move down to (2,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 0 0 0

Why: Down cell is open, continue path

Step 6: Move down to (3,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 0 0

Why: Down cell is open, continue path

Step 7: Move right to (3,2), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 0

Why: Right cell is open, continue path

Step 8: Move right to (3,3), mark as part of path - goal reached

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Why: Reached goal cell, path found

Result:

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1
Path found from start to goal

Annotated Code

DSA C

#include <stdio.h>
#define N 4

int isSafe(int maze[N][N], int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
        sol[x][y] = 1; // mark goal cell
        return 1;
    }

    if (isSafe(maze, x, y) == 1) {
        if (sol[x][y] == 1) // already part of path
            return 0;

        sol[x][y] = 1; // mark current cell as part of path

        if (solveMazeUtil(maze, x + 1, y, sol) == 1) // move down
            return 1;

        if (solveMazeUtil(maze, x, y + 1, sol) == 1) // move right
            return 1;

        sol[x][y] = 0; // backtrack
        return 0;
    }

    return 0;
}

void printSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", sol[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int maze[N][N] = {
        {1, 0, 0, 0},
        {1, 1, 0, 0},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0};

    if (solveMazeUtil(maze, 0, 0, sol) == 1) {
        printSolution(sol);
    } else {
        printf("No path found\n");
    }

    return 0;
}

if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {

Check if current cell is goal and open

sol[x][y] = 1; // mark current cell as part of path

Mark cell as part of solution path

if (solveMazeUtil(maze, x + 1, y, sol) == 1) // move down

Try moving down recursively

if (solveMazeUtil(maze, x, y + 1, sol) == 1) // move right

Try moving right recursively

sol[x][y] = 0; // backtrack

Remove cell from path if no way forward

Output

1 0 0 0 

1 1 0 0 

0 1 0 0 

0 1 1 1 

Complexity Analysis

Time: O(2^(N*N)) because in worst case each cell can lead to two recursive calls exploring all paths

Space: O(N*N) for the solution matrix and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and can find shortest path, this DFS approach explores paths deeply and may be slower but simpler to implement

Edge Cases

Empty maze (all zeros)

No path found, function returns 0

DSA C

if (isSafe(maze, x, y) == 1) {

Start or goal cell blocked

No path found immediately

DSA C

if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {

Single cell maze open

Path found immediately

DSA C

if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from start to end, use backtracking to explore possible routes step-by-step.

Common Mistakes

Mistake: Not marking visited cells causing infinite recursion
Fix: Mark cells as part of path before recursive calls and unmark on backtrack

Mistake: Trying to move outside grid boundaries
Fix: Check boundaries with isSafe before moving

Summary

Finds a path through a maze grid from start to goal by moving only through open cells.

Use when you need to explore all possible paths in a grid to find a valid route.

The key is to try moves step-by-step, mark path, and backtrack if stuck.