L19. Rat in a Maze | Backtracking

1. Why Do We Need Backtracking for the Rat in a Maze?

The Rat in a Maze problem is a classic algorithmic challenge where a rat starts at the top-left corner of a grid (0, 0) and must find a path to the bottom-right destination cell (N-1, N-1).

The Core Problem Statement

• Grid Dimensions: An $N \times N$ square matrix.
• Start Position: (0, 0)
• Destination: (N-1, N-1)
• Allowed Movements: Down (D), Left (L), Right (R), and Up (U).
• Cell Constraints:
  • 1 represents an open, traversable path.
  • 0 represents a blocked cell or wall that the rat cannot enter.
• Visited Constraint: A cell cannot be visited more than once in the same path to prevent infinite loops.
• Ordering Requirement: If multiple paths exist, output them in lexicographical order (alphabetical order of directions: D, L, R, U).

2. Core Mental Model and Exploration Strategy

To solve this problem, we must explore every possible combination of moves from the start cell until we reach the destination. Since we need all valid paths, a greedy approach or dynamic programming will not work; we need Recursion and Backtracking.

Real-Life Analogy: Navigating a Maze with a Ball of String

Analogy: Imagine exploring a complex cave system (a maze) with multiple branching corridors. You walk down a path, marking your steps with chalk and string behind you. If you hit a dead end, you realize, "I cannot go any further here." You retrace your steps (backtrack) while untying your string, removing your chalk marks, and return to the last junction to try a different direction (e.g., trying Left instead of Down).

3. The Lexicographical Order Requirement

The problem specifies that if multiple paths exist, we must print them in lexicographical (alphabetical) order.

To achieve this naturally without sorting post-computation, our recursive exploration function must try directions in a strict alphabetical order:

1. D (Down)
2. L (Left)
3. R (Right)
4. U (Up)

By exploring D first, then L, then R, and finally U, any valid path string generated will naturally be formed in correct alphabetical sequence.

4. Step-by-Step Path Evolution Walkthrough

Let's trace how a rat evaluates choices on a grid. Suppose the rat is at position (i, j) and considers all four directions:

• Moving Down (D): Row index increases by 1 (i + 1, j)
• Moving Left (L): Column index decreases by 1 (i, j - 1)
• Moving Right (R): Column index increases by 1 (i, j + 1)
• Moving Up (U): Row index decreases by 1 (i - 1, j)

The State Modification & Backtracking Cycle

1. Check Validity: Ensure the target cell is within matrix bounds, contains a 1, and has not been visited yet in the current path.
2. Mark as Visited: Temporarily set the current cell in the visited matrix to 1 (or mark matrix[i][j] = 0 to block re-entry).
3. Recursive Call: Append the move character (D, L, R, or U) to the path string and recurse on the new cell.
4. Backtrack (Undo): Upon returning from the recursive call, unmark the cell (matrix[i][j] = 1) so other alternative paths can utilize this cell.

5. Handling Boundaries, Walls, and Visited States

Before making any move into a neighboring cell (next_i, next_j), four critical validation checks must pass:

If any condition fails, that specific direction is immediately abandoned.

6. Complete Flow Walkthrough of Recursive Exploration

Let's examine the recursive state transitions for a sample run:

7. Naive Approach vs. Optimized Clean Implementation

Writing separate recursive calls for all four directions leads to repetitive, bloated code (around 50-60 lines of redundant boundary checks).

The Optimized Direction Array Technique

Instead of writing 4 distinct blocks of code for D, L, R, and U, professional developers use Direction Arrays (dr and dc).

// Direction vectors for Down, Left, Right, Up in lexicographical order
string moveDir = "DLRU";
int dr[] = { 1,  0, 0, -1 };
int dc[] = { 0, -1, 1,  0 };

This lets us loop through all 4 directions cleanly in a single for loop.

8. Complete C++ Implementation

Below is the clean, production-grade implementation of the Rat in a Maze problem using backtracking and direction arrays.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
private:
    void findPaths(int i, int j, vector<vector<int>>& m, int n, vector<string>& ans, string move, vector<vector<int>>& vis) {
        // Base Case: If we reach the destination
        if (i == n - 1 && j == n - 1) {
            ans.push_back(move);
            return;
        }

        // Direction arrays for Down, Left, Right, Up (Lexicographical order: D, L, R, U)
        string dirStr = "DLRU";
        int di[] = { 1,  0, 0, -1 };
        int dj[] = { 0, -1, 1,  0 };

        // Mark current cell as visited
        vis[i][j] = 1;

        // Explore all 4 directions
        for (int idx = 0; idx < 4; idx++) {
            int next_i = i + di[idx];
            int next_j = j + dj[idx];

            // Check if the next move is valid
            if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < n && !vis[next_i][next_j] && m[next_i][next_j] == 1) {
                findPaths(next_i, next_j, m, n, ans, move + dirStr[idx], vis);
            }
        }

        // Backtrack: Unmark current cell before returning
        vis[i][j] = 0;
    }

public:
    vector<string> findPath(vector<vector<int>>& m, int n) {
        vector<string> ans;
        vector<vector<int>> vis(n, vector<int>(n, 0)); // Visited matrix initialized to 0

        // If the starting or ending point is blocked, no path is possible
        if (m[0][0] == 1 && m[n - 1][n - 1] == 1) {
            findPaths(0, 0, m, n, ans, "", vis);
        }

        return ans;
    }
};

int main() {
    int n = 4;
    vector<vector<int>> m = {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {1, 1, 0, 0},
        {0, 1, 1, 1}
    };

    Solution obj;
    vector<string> result = obj.findPath(m, n);

    cout << "Possible Paths:\n";
    for (const string& path : result) {
        cout << path << endl;
    }

    return 0;
}

9. Complexity Analysis

Summary and Key Takeaways

• Backtracking Paradigm: Backtracking allows us to explore choices, test feasibility, and undo our state when hitting dead ends so we can explore alternate paths.
• Lexicographical Order: By ordering our movement explorations strictly as Down (D) $\rightarrow$ Left (L) $\rightarrow$ Right (R) $\rightarrow$ Up (U), valid paths naturally emerge in alphabetical order.
• State Restoration (Unmarking): Crucially, after exploring a recursive branch, we must reset vis[i][j] = 0 (backtrack) so that other valid paths passing through this intersection are not blocked.
• Edge Case Validation: Always verify that the starting cell m[0][0] and destination cell m[N-1][N-1] are open (1) before initiating recursive exploration.
• Direction Arrays: Using offset arrays (di and dj) drastically reduces code duplication and streamlines multidirectional traversal logic in grid-based problems.