Code: Rat in a Maze using Recursion | DSA in C++ - Software Development PDF Download

Here's an example code in C++ to solve the Rat in a Maze problem using recursion:

#include <iostream>

#include <vector>

using namespace std;

const int N = 4;  // Size of the maze

// Function to print the solution matrix

void printSolution(const vector<vector<int>>& solution) {

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            cout << solution[i][j] << " ";

        }

        cout << endl;

    }

}

// Recursive function to solve the Rat in a Maze problem

bool solveMazeUtil(const vector<vector<int>>& maze, vector<vector<int>>& solution, int x, int y) {

    // Check if (x, y) is a valid cell

    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) {

        // Check if we have reached the destination (bottom-right cell)

        if (x == N - 1 && y == N - 1) {

            solution[x][y] = 1;  // Mark the destination cell as part of the solution path

            return true;

        }

        // Mark the current cell as part of the solution path

        solution[x][y] = 1;

        // Move down

        if (solveMazeUtil(maze, solution, x + 1, y))

            return true;

        // Move right

        if (solveMazeUtil(maze, solution, x, y + 1))

            return true;

        // If none of the above movements work, backtrack

        solution[x][y] = 0;

        return false;

    }

    return false;

}

// Function to solve the Rat in a Maze problem

void solveMaze(const vector<vector<int>>& maze) {

    vector<vector<int>> solution(N, vector<int>(N, 0));  // Create a solution matrix

    if (solveMazeUtil(maze, solution, 0, 0)) {

        cout << "Path found! Solution:" << endl;

        printSolution(solution);

    } else {

        cout << "No path found!" << endl;

    }

}

int main() {

    vector<vector<int>> maze = {

        {1, 0, 0, 0},

        {1, 1, 0, 1},

        {0, 1, 0, 0},

        {1, 1, 1, 1}

    };

    solveMaze(maze);

    return 0;

}

Output:

Path found! Solution:

1 0 0 0 

1 1 0 0 

0 1 0 0 

0 1 1 1

Explanation:

• The Rat in a Maze problem is a classic example of backtracking, where we need to find a path from the top-left cell to the bottom-right cell in a maze.
• In the code, we first define the size of the maze as 'N'. The maze is represented by a 2D vector 'maze', where 'maze'[i][j]' represents the cell at row 'i' and column 'j'. The value '1' represents an open cell, while '0' represents a blocked cell.
• The 'printSolution' function is a utility function that prints the solution matrix, which represents the path taken by the rat.
• The 'solveMazeUtil' function is a recursive helper function that implements the backtracking algorithm. It takes the current maze, the solution matrix, and the current position '(x, y)' as input. The function first checks if the current position is valid and an open cell. If it is, it checks if the current position is the destination. If it is, it marks the cell as part of the solution path and returns 'true' to indicate that a path has been found.
• If the current position is not the destination, the function tries to move down (x + 1) and recursively calls 'solveMazeUtil' with the updated position. If moving down does not lead to a solution, it tries to move right (y + 1) and recursively calls 'solveMazeUtil' again. If neither movement works, it backtracks by marking the current cell as not part of the solution path ('solution[x][y] = 0') and returns 'false' to indicate that no path was found.
• The 'solveMaze' function initializes the solution matrix and calls 'solveMazeUtil' with the starting position '(0, 0)'. If a path is found, it prints the solution matrix using 'printSolution'. Otherwise, it prints "No path found!".
• In the 'main' function, we define the maze as a 2D vector and call 'solveMaze' to find the path. The given maze has a valid path from the top-left cell '(0, 0)' to the bottom-right cell '(N-1, N-1)'. The solution is printed as a matrix, where '1' represents the path taken by the rat.

The code uses recursion to explore all possible paths in the maze, backtracking whenever a path does not lead to the destination. The backtracking approach ensures that all possible paths are considered, and the first valid path found is returned as the solution.