🐀 Rat in a Maze – Complete In-Depth Explanation

The "Rat in a Maze" is a classic problem where a rat needs to find a path from the starting cell to the destination cell in a maze. The maze is represented by a 2D grid, where some cells are blocked (walls) and some are open (paths).

📌 Why is Rat in a Maze Important?

• 💡 Demonstrates backtracking algorithms.
• 🧩 Illustrates pathfinding problems.
• ⚙️ Good example for understanding recursion.

📌 Understanding Rat in a Maze with an Example

Consider the following maze:

                  1 1 1 1
                  1 0 1 1
                  1 0 1 1
                  1 1 1 1
                

Here, '1' represents an open path, and '0' represents a wall. The rat starts at the top-left cell (0, 0) and needs to reach the bottom-right cell (3, 3).

One possible solution path is:

                  1 1 1 1
                  1 * 1 1
                  1 * 1 1
                  1 1 1 1
                

Where '*' represents the path taken by the rat.

🔹 Key Points

• The rat can move in four directions: up, down, left, and right.
• The rat cannot move diagonally.
• The rat cannot move through walls (cells with '0').
• The rat must find a path to the destination cell.

🛠 Solution Approach (Backtracking)

The most common approach to solve the Rat in a Maze problem is using backtracking:

1. Start at the starting cell.
2. Try moving in one direction (e.g., down).
3. If the move is valid (not a wall and within the maze boundaries), mark the cell as part of the path and recursively try to reach the destination from the new cell.
4. If the recursive call is successful (reaches the destination), return true.
5. If the recursive call is not successful (cannot reach the destination from the new cell), backtrack: unmark the cell (remove it from the path) and try a different direction.
6. If all directions have been tried and none lead to the destination, return false.

                  #include 
                  #include 
              
                  using namespace std;
              
                  bool isSafe(int row, int col, vector>& maze, int n) {
                      return (row >= 0 && row < n && col >= 0 && col < n && maze[row][col] == 1);
                  }
              
                  bool solveMazeUtil(vector>& maze, int row, int col, vector>& path, int n) {
                      if (row == n - 1 && col == n - 1) { // Reached the destination
                          path[row][col] = 1;
                          return true;
                      }
              
                      if (isSafe(row, col, maze, n)) {
                          path[row][col] = 1;
              
                          // Try moving down
                          if (solveMazeUtil(maze, row + 1, col, path, n)) return true;
              
                          // Try moving right
                          if (solveMazeUtil(maze, row, col + 1, path, n)) return true;
              
                          // Try moving up
                          if (solveMazeUtil(maze, row - 1, col, path, n)) return true;
              
                          // Try moving left
                          if (solveMazeUtil(maze, row, col - 1, path, n)) return true;
              
                          path[row][col] = 0; // Backtrack: Unmark the cell
                          return false;
                      }
                      return false;
                  }
              
                  bool solveMaze(vector>& maze, int n) {
                      vector> path(n, vector(n, 0));
                      if (solveMazeUtil(maze, 0, 0, path, n)) {
                          cout << "Solution found:\n";
                          for (int i = 0; i < n; i++) {
                              for (int j = 0; j < n; j++) {
                                  cout << path[i][j] << " ";
                              }
                              cout << endl;
                          }
                          return true;
                      } else {
                          cout << "No solution exists.\n";
                          return false;
                      }
                  }
              
                  int main() {
                      int n = 4;
                      vector> maze = {
                          {1, 1, 1, 1},
                          {1, 0, 1, 1},
                          {1, 0, 1, 1},
                          {1, 1, 1, 1}
                      };
              
                      solveMaze(maze, n);
              
                      return 0;
                  }
                

⏳ Time Complexity Analysis

The time complexity of the backtracking solution can be exponential in the worst case, as we might explore all possible paths. However, in practice, the actual execution time is often much less due to pruning (not exploring paths that are obviously blocked).

🌍 Real-World Applications of Pathfinding

• 🗺 Navigation systems (GPS).
• 🤖 Robotics.
• 🎮 Game development (AI characters).

🔗 Next Topics

• 🔙 Backtracking
• 🚶 Pathfinding Algorithms