Rat in a Maze: Interactive Pathfinding Algorithm with Backtracking

Description

The Rat in a Maze is a classic backtracking problem where a rat needs to find a path from the source (top-left corner) to the destination (bottom-right corner) in a maze. The maze is represented as a binary matrix where 1 represents a valid path and 0 represents a blocked path.

How It Works

Start from the source cell (0,0)
The rat can move in four directions: right, down, left, or up
For each move:
- Check if the move is valid (within bounds and not blocked)
- Mark the current cell as part of the path
- Recursively try to reach the destination from the new position
- If the recursive call fails, backtrack by unmarking the current cell
If the destination is reached, a path is found
If no direction leads to the destination, return false

Visualization

Size:

Speed:

Click on cells to toggle walls, then click Start

Implementation


def solve_maze(maze):
    n = len(maze)
    # Solution matrix initialized with 0's
    sol = [[0 for _ in range(n)] for _ in range(n)]
    
    if solve_maze_util(maze, 0, 0, sol, n):
        return sol
    return None

def is_safe(maze, x, y, n):
    return (x >= 0 and x < n and 
            y >= 0 and y < n and 
            maze[x][y] == 1)

def solve_maze_util(maze, x, y, sol, n):
    # If (x, y) is the destination, return True
    if x == n-1 and y == n-1:
        sol[x][y] = 1
        return True
    
    if is_safe(maze, x, y, n):
        # Mark current cell as part of solution path
        sol[x][y] = 1
        
        # Try moving right
        if solve_maze_util(maze, x, y+1, sol, n):
            return True
        
        # Try moving down
        if solve_maze_util(maze, x+1, y, sol, n):
            return True
        
        # Try moving left
        if solve_maze_util(maze, x, y-1, sol, n):
            return True
        
        # Try moving up
        if solve_maze_util(maze, x-1, y, sol, n):
            return True
        
        # If no direction works, backtrack
        sol[x][y] = 0
        return False
    
    return False


class RatMaze {
private:
    bool isSafe(vector<vector<int>>& maze, int x, int y, int n) {
        return (x >= 0 && x < n && 
                y >= 0 && y < n && 
                maze[x][y] == 1);
    }
    
    bool solveMazeUtil(vector<vector<int>>& maze, 
                       int x, int y, 
                       vector<vector<int>>& sol, 
                       int n) {
        // Base case: destination reached
        if (x == n-1 && y == n-1) {
            sol[x][y] = 1;
            return true;
        }
        
        if (isSafe(maze, x, y, n)) {
            sol[x][y] = 1;
            
            // Try moving right
            if (solveMazeUtil(maze, x, y+1, sol, n))
                return true;
            
            // Try moving down
            if (solveMazeUtil(maze, x+1, y, sol, n))
                return true;
            
            // Try moving left
            if (solveMazeUtil(maze, x, y-1, sol, n))
                return true;
            
            // Try moving up
            if (solveMazeUtil(maze, x-1, y, sol, n))
                return true;
            
            // Backtrack
            sol[x][y] = 0;
            return false;
        }
        
        return false;
    }
    
public:
    vector<vector<int>> solveMaze(vector<vector<int>>& maze) {
        int n = maze.size();
        vector<vector<int>> sol(n, vector<int>(n, 0));
        
        if (solveMazeUtil(maze, 0, 0, sol, n))
            return sol;
            
        return vector<vector<int>>();
    }
};


public class RatMaze {
    private bool IsSafe(int[,] maze, int x, int y, int n) {
        return (x >= 0 && x < n && 
                y >= 0 && y < n && 
                maze[x,y] == 1);
    }
    
    private bool SolveMazeUtil(int[,] maze, int x, int y, 
                              int[,] sol, int n) {
        // Base case: destination reached
        if (x == n-1 && y == n-1) {
            sol[x,y] = 1;
            return true;
        }
        
        if (IsSafe(maze, x, y, n)) {
            sol[x,y] = 1;
            
            // Try moving right
            if (SolveMazeUtil(maze, x, y+1, sol, n))
                return true;
            
            // Try moving down
            if (SolveMazeUtil(maze, x+1, y, sol, n))
                return true;
            
            // Try moving left
            if (SolveMazeUtil(maze, x, y-1, sol, n))
                return true;
            
            // Try moving up
            if (SolveMazeUtil(maze, x-1, y, sol, n))
                return true;
            
            // Backtrack
            sol[x,y] = 0;
            return false;
        }
        
        return false;
    }
    
    public int[,] SolveMaze(int[,] maze) {
        int n = (int)Math.Sqrt(maze.Length);
        int[,] sol = new int[n,n];
        
        if (SolveMazeUtil(maze, 0, 0, sol, n))
            return sol;
            
        return null;
    }
}

Complexity Analysis

Time Complexity

The time complexity of the Rat in a Maze algorithm is O(2^(n*n)), where n is the size of the maze. This is because:

At each cell, we have up to 4 possible moves
We may need to explore every possible path
The maximum path length is n*n cells
Each cell needs to be checked for validity (O(1))

Space Complexity

The space complexity is O(n*n), where n is the maze size. This includes:

The solution matrix to track the path
The recursion stack (maximum depth n*n)
The original maze matrix

Advantages and Disadvantages

Advantages

Guaranteed to find a path if one exists
Simple implementation using recursion
Can be modified to find all possible paths
Works with any maze configuration
Memory efficient for small mazes

Disadvantages

Exponential time complexity
May be slow for large mazes
Not optimal for finding shortest path
Stack overflow possible for very large mazes
Performance degrades with maze complexity

Quick Info

Rat in a Maze