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.