Maze Solving with Backtracking

1. Understanding the "Rat in a Maze" Problem

Imagine a rat placed in the top-left corner (0, 0) of a square grid or maze. The rat needs to find a path to the bottom-right corner (n-1, n-1).

Here are the rules:

• The maze is represented by a binary matrix (a 2D array of 0s and 1s).
• A 1 represents a cell the rat can move to (an open path).
• A 0 represents a cell the rat cannot move into (a blocked wall).
• The rat can move in four directions: Up (U), Down (D), Left (L), and Right (R).
• The rat cannot move into a cell more than once in a single path.

Our goal is to find all possible paths the rat can take from the source to the destination.

2. From Simple Recursion to Backtracking

Let's start with a simplified version. If the rat could only move Down and Right, there would be no risk of getting stuck in a loop. We could simply use recursion to explore both options from every cell.

However, when we allow movement in all four directions, a major problem arises: cycles. The rat could move Right, then Left, then Right, then Left, getting stuck in an infinite loop.

How do we prevent this? We must keep track of the cells we have already visited within the current path. This is the key insight that transforms a simple recursive solution into a backtracking one.

The following video provides an excellent explanation of this evolution. It starts with the simple case (Down/Right), introduces obstacles, and then expands to four directions, clearly explaining why a "visited" check is necessary and how backtracking works by "un-marking" cells.

3. The Backtracking Algorithm for the Maze

As the video explained, our choose, explore, unchoose pattern fits perfectly here. For any given cell (r, c):

1. Base Case: If the rat is at the destination (n-1, n-1), we've found a valid path. We record this path and return.
2. Choose: We are now considering the current cell (r, c) as part of our path. We must mark it as visited to avoid cycles.
3. Explore: We try to move to all valid adjacent cells (Up, Down, Left, Right). A move is valid if the new cell is:
   • Within the grid boundaries.
   • Not a blocked cell (its value is 1).
   • Not already visited in the current path.
     For each valid move, we make a recursive call.
4. Unchoose: After the recursive calls for all four directions have returned (meaning we've fully explored all paths from (r, c)), we un-mark the cell (r, c) as visited. This is the crucial backtracking step. It frees up this cell to be used in other potential paths.

The video below offers a fantastic visual walkthrough of this process. You'll see the algorithm explore paths, hit dead ends, backtrack, and try new routes.

4. Java Implementation

Now, let's translate this logic into Java code. A common and efficient technique for grid problems is to use "delta" arrays to represent the four directions. Instead of four separate if statements for U, D, L, R, we can use a loop.

• dr = {1, 0, 0, -1} (change in row for D, L, R, U)
• dc = {0, -1, 1, 0} (change in column for D, L, R, U)
• dir = "DLRU"

This way, the i-th element of each array corresponds to the same direction. For example, (dr[0], dc[0]) gives (1, 0), which is the "Down" move.

The following resource provides a clean, full implementation using this technique.

Here is the core logic from that article, annotated to highlight the backtracking pattern:

class RatInAMazeSolver {

    // Arrays to represent the 4 directions: Down, Left, Right, Up
    static String dir = "DLRU";
    static int[] dr = {1, 0, 0, -1};
    static int[] dc = {0, -1, 1, 0};

    // Helper to check if a cell is within bounds, not blocked, and not visited
    static boolean isValid(int r, int c, int n, int[][] maze) {
        // Here, maze[r][c] == 1 also checks if it's not visited, 
        // since we mark visited cells as 0.
        return r >= 0 && c >= 0 && r < n && c < n && maze[r][c] == 1;
    }

    static void findPath(int r, int c, int[][] maze, StringBuilder path, ArrayList<String> res) {
        int n = maze.length; 

        // BASE CASE: If destination is reached, store the path and return.
        if (r == n - 1 && c == n - 1) {
            res.add(path.toString());
            return;
        }
        
        // CHOOSE: Mark the current cell as visited.
        // Here, we modify the maze itself. 0 means "blocked" or "visited".
        maze[r][c] = 0; 

        // EXPLORE: Iterate through all 4 possible directions.
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i]; // next row
            int nc = c + dc[i]; // next column
            
            if (isValid(nr, nc, n, maze)) {
                path.append(dir.charAt(i)); // Add move to path string
                
                // Recursive call for the next cell
                findPath(nr, nc, maze, path, res); 
                
                // Backtrack on the path string
                path.deleteCharAt(path.length() - 1);
            }
        }
        
        // UNCHOOSE: Un-mark current cell, making it available for other paths.
        maze[r][c] = 1;  
    }

    // Main wrapper function
    static ArrayList<String> ratInMaze(int[][] maze) {
        // ... setup and initial call to findPath(0, 0, ...) ...
        // ... sort results lexicographically ...
        return new ArrayList<String>(); // Simplified for example
    }
}

5. Complexity Analysis

• Time Complexity: O(4^(n*n))
  This is a loose upper bound. In the worst case, we might have to explore 4 directions from each of the n*n cells. The actual number of paths is much smaller due to blocked cells and the "no-revisit" rule, but this notation captures the exponential nature of the search space.

• Space Complexity: O(n*n)
  The main space cost is the recursion call stack. In the worst case, the path could be very long, winding through every single cell of the maze. Therefore, the maximum depth of the recursion could be n*n.

Conclusion

Congratulations! You have now mastered another classic backtracking problem. You've seen how the same core principles from Sudoku can be adapted to navigate a maze, handle cycles, and find all possible solutions.

Key Takeaways:

• Maze-solving is a natural application for backtracking.
• The choose, explore, unchoose pattern maps to: mark as visited, recursively explore neighbors, and un-mark as visited.
• Using a visited array (or modifying the maze itself) is crucial to prevent infinite loops.
• The dr/dc direction arrays are a clean and scalable way to handle grid-based movement in your code, a valuable trick for technical interviews.

Preview of the Next Module:
This lesson concludes our deep dive into backtracking. The maze problem serves as a perfect bridge to our next topic: Graphs. A maze can be thought of as a graph where each cell is a node and each valid move is an edge. The backtracking search we just performed is a form of Depth-First Search (DFS), a fundamental graph traversal algorithm.

In the next module, we'll start by learning how to formally represent graphs in code using adjacency matrices and adjacency lists, laying the foundation for exploring powerful graph algorithms like BFS and DFS.