Rat in a Maze Problem in DSA C - Build from Scratch

Rat in a Maze Problem

📖 Scenario: Imagine a small rat trying to find its way through a maze to reach the cheese. The maze is a grid where some cells are open paths and others are walls. The rat can only move right or down. We want to help the rat find a path from the top-left corner to the bottom-right corner.

🎯 Goal: Build a program that represents the maze as a 2D array, sets up a solution grid, uses a function to find a path for the rat, and finally prints the path taken by the rat through the maze.

📋 What You'll Learn

Create a 4x4 maze as a 2D array with specific open and blocked cells

Create a 4x4 solution grid initialized to zero

Write a function called solveMaze that finds a path from start to finish

Print the solution grid showing the path with 1s and other cells as 0

💡 Why This Matters

🌍 Real World

Maze solving algorithms are used in robotics for path planning and navigation in unknown environments.

💼 Career

Understanding recursive backtracking and grid traversal is important for software roles involving algorithms, game development, and AI.

1

Create the maze grid

Create a 4x4 integer array called maze with these exact values: {{1, 0, 0, 0}, {1, 1, 0, 1}, {0, 1, 0, 0}, {1, 1, 1, 1}}

DSA C

# Create the 4x4 maze array with the given values
// Your code here

Hint

Use a 2D array with 4 rows and 4 columns. Each row is enclosed in curly braces and separated by commas.

2

Create the solution grid

Create a 4x4 integer array called solution and initialize all elements to 0

DSA C

int maze[4][4] = {
    {1, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 1, 0, 0},
    {1, 1, 1, 1}
};

// Create the 4x4 solution array initialized to 0
// Your code here

Hint

Use int solution[4][4] = {0}; to initialize all elements to zero.

3

Write the solveMaze function

Write a function called solveMaze that takes maze, solution, x, and y as parameters and returns 1 if a path is found, 0 otherwise. The function should check if the current cell is safe, mark it in solution, and recursively try moving right or down.

DSA C

int maze[4][4] = {
    {1, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 1, 0, 0},
    {1, 1, 1, 1}
};

int solution[4][4] = {0};

// Write the solveMaze function below
// Your code here

Hint

Use recursion to try moving right (x+1, y) and down (x, y+1). Mark the path in solution and backtrack if needed.

4

Print the solution path

Call solveMaze with maze, solution, 0, 0 and then print the solution grid row by row, with spaces between numbers.

DSA C

int maze[4][4] = {
    {1, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 1, 0, 0},
    {1, 1, 1, 1}
};

int solution[4][4] = {0};

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

int solveMaze(int maze[4][4], int solution[4][4], int x, int y) {
    if (x == 3 && y == 3 && maze[x][y] == 1) {
        solution[x][y] = 1;
        return 1;
    }

    if (isSafe(maze, x, y) == 1) {
        if (solution[x][y] == 1) {
            return 0;
        }

        solution[x][y] = 1;

        if (solveMaze(maze, solution, x + 1, y) == 1) {
            return 1;
        }

        if (solveMaze(maze, solution, x, y + 1) == 1) {
            return 1;
        }

        solution[x][y] = 0;
        return 0;
    }

    return 0;
}

// Call solveMaze and print the solution grid
// Your code here

Hint

Call solveMaze(maze, solution, 0, 0). If it returns 1, print the solution array row by row with spaces between numbers.

Practice

1. What is the main goal of the Rat in a Maze problem?

easy

A. Calculate the shortest distance between two points in a maze

B. Count the number of walls in the maze

C. Find a path from the start to the destination in a maze

D. Fill the maze with numbers

Solution

1. Step 1: Understand the problem statement

   The Rat in a Maze problem asks to find a path from the start (usually top-left) to the destination (usually bottom-right) in a maze represented by a grid.

2. Step 2: Identify the goal

   The goal is to find any valid path through open cells (usually marked 1) avoiding blocked cells (usually marked 0).

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option C

4. Quick Check:

   Goal = Find path [OK]

Hint: Look for pathfinding from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming maze filling is required

2. Which of the following is the correct way to declare the maze matrix in C for a 4x4 maze?

easy

A. int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}};

B. int maze[4] = {1,0,0,0,1,1,0,1,0,1,0,0,1,1,1,1};

C. int maze[][] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}};

D. int maze[4][4] = {1,0,0,0,1,1,0,1,0,1,0,0,1,1,1};

Solution

1. Step 1: Understand C array declaration syntax

   In C, a 2D array must have both dimensions specified except for the first dimension if initialized immediately. Here, both dimensions are specified as 4.

2. Step 2: Check initialization format

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; correctly declares a 4x4 int array with nested braces for each row.

3. Final Answer:

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; [OK]

Hint: Use nested braces for each row in 2D array initialization [OK]

Common Mistakes:

• Omitting second dimension size
• Using single braces for all elements
• Declaring incomplete array sizes

3. What will be the output of the following code snippet for the Rat in a Maze problem?

int maze[4][4] = {
  {1, 0, 0, 0},
  {1, 1, 0, 1},
  {0, 1, 0, 0},
  {1, 1, 1, 1}
};

int solution[4][4] = {0};

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    solution[x][y] = 0;
    return 0;
  }
  return 0;
}

int main() {
  if (solveMaze(maze, 0, 0, solution)) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        printf("%d ", solution[i][j]);
      }
      printf("\n");
    }
  } else {
    printf("No path found\n");
  }
  return 0;
}

medium

A. 1 0 0 0
0 1 0 0
0 1 0 0
0 1 1 1

B. 1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

C. No path found

D. 1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Solution

1. Step 1: Trace the recursive calls

   The function tries to move right (x+1, y) first, then down (x, y+1). It marks path cells in solution matrix if maze cell is 1.

2. Step 2: Follow the path found

   Starting at (0,0), path moves down to (1,0), then right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). This path is marked with 1s in solution.

3. Final Answer:

   1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 -> Option D

4. Quick Check:

   Path marked in solution matrix = 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 [OK]

Hint: Trace recursion path marking 1s in solution matrix [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming path includes blocked cells
• Ignoring backtracking step

4. Identify the bug in the following solveMaze function and select the correct fix.

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    return 0;
  }
  return 0;
}

medium

A. Change base case to check (x == 4 && y == 4)

B. Add backtracking step: set solution[x][y] = 0 before returning 0

C. Remove the check maze[x][y] == 1

D. Change recursive calls order to (x, y + 1) then (x + 1, y)

Solution

1. Step 1: Identify missing backtracking

   The function marks solution[x][y] = 1 but does not reset it to 0 if path fails, causing incorrect path marking.

2. Step 2: Fix by adding backtracking

   Before returning 0, set solution[x][y] = 0 to unmark the cell and allow other paths to be explored.

3. Final Answer:

   Add backtracking step: set solution[x][y] = 0 before returning 0 -> Option B

4. Quick Check:

   Backtracking needed to unmark path [OK]

Hint: Always unmark path cell if dead end found [OK]

Common Mistakes:

• Forgetting to unmark solution cell
• Incorrect base case coordinates
• Changing recursion order without reason

5. Given a 5x5 maze where 0 represents blocked cells and 1 represents open cells, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to end (4,4)?

hard

A. Modify the function to explore all directions and store each valid path in a list

B. Stop recursion after finding the first path and return immediately

C. Use a queue instead of recursion to find one path only

D. Change maze values from 1 to 2 to mark visited cells permanently

Solution

1. Step 1: Understand requirement to find all paths

   Finding all paths means exploring every possible route from start to end without stopping at first success.

2. Step 2: Modify algorithm to explore all directions and store paths

   Change recursion to continue after finding a path, store each valid path in a list or array, and backtrack properly to explore other routes.

3. Final Answer:

   Modify the function to explore all directions and store each valid path in a list -> Option A

4. Quick Check:

   All paths require full exploration [OK]

Hint: Explore all routes and save paths, don't stop at first success [OK]

Common Mistakes:

• Stopping after first path found
• Marking visited cells permanently blocking other paths
• Using BFS without path storage