Embarking on a daily coding challenge is an excellent way to hone problem-solving abilities and deepen understanding of algorithms. Today’s focus is on a classic pathfinding problem from GeeksforGeeks: “Rat in a Maze”. This medium-difficulty problem serves as a fantastic exercise in applying backtracking algorithms.

The Rat in a Maze Problem: Navigating a Grid

Imagine a rat placed at the top-left corner (0, 0) of an N x N grid, or “maze.” Its ultimate goal is to reach the bottom-right corner (N-1, N-1). The maze itself is composed of cells, each marked with either a ‘0’ or a ‘1’. A ‘0’ signifies a blocked cell that the rat cannot traverse, while a ‘1’ indicates a free cell it can move through.

The rat has four possible directions of movement: ‘U’ (Up), ‘D’ (Down), ‘L’ (Left), and ‘R’ (Right). The critical conditions for its journey are:
* It can only move to adjacent cells within the maze boundaries.
* It cannot move through blocked cells (‘0’).
* Crucially, the rat cannot revisit any cell along the same path to prevent infinite loops and find distinct routes.

The objective is to discover all possible valid paths the rat can take from its starting point to the destination. If no such path exists, an empty list should be returned. The final list of paths must be presented in lexicographically smallest order.

Illustrative Examples:

Example 1:
Input: maze[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
Output: ["DDRDRR", "DRDDRR"]
Explanation: From (0,0) to (3,3), two distinct paths are found: “DDRDRR” and “DRDDRR”.

Example 2:
Input: maze[][] = [[1, 0], [1, 0]]
Output: []
Explanation: No path exists to the destination (1, 1) as it’s blocked.

Example 3:
Input: maze[][] = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: ["DDRR", "RRDD"]
Explanation: The rat has two possible paths to reach the destination: “DDRR” and “RRDD”.

Constraints:

• The maze size n will be between 2 and 5 (inclusive).
• Each cell maze[i][j] will be either 0 or 1.

Pythonic Backtracking Solution

The “Rat in a Maze” problem is a classic application of backtracking and Depth-First Search (DFS). The core idea is to explore every possible path. When a path leads to a dead end or a blocked cell, we “backtrack” to the last decision point and try an alternative route.

Solution Breakdown:

The provided Python solution effectively implements this backtracking strategy:

class Solution:
    def ratInMaze(self, maze):
        n = len(maze)
        res = []
        # Edge case: If start or end is blocked, no path exists
        if maze[0][0] == 0 or maze[n-1][n-1] == 0:
            return res

        # 'vis' matrix to keep track of visited cells in the current path
        vis = [[0]*n for _ in range(n)]

        # DFS helper function to explore paths
        def dfs(i, j, path):
            # Base case: If destination is reached, add path to results
            if i == n-1 and j == n-1:
                res.append(path)
                return

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

            # Explore all 4 possible directions (D, L, R, U)
            # D (Down)
            if i+1 < n and not vis[i+1][j] and maze[i+1][j]:
                dfs(i+1, j, path+'D')
            # L (Left)
            if j-1 >= 0 and not vis[i][j-1] and maze[i][j-1]:
                dfs(i, j-1, path+'L')
            # R (Right)
            if j+1 < n and not vis[i][j+1] and maze[i][j+1]:
                dfs(i, j+1, path+'R')
            # U (Up)
            if i-1 >= 0 and not vis[i-1][j] and maze[i-1][j]:
                dfs(i-1, j, path+'U')

            # Backtrack: Unmark current cell as visited for other paths
            vis[i][j] = 0

        # Start DFS from (0,0) with an empty path
        dfs(0, 0, '')

        # Return sorted paths lexicographically
        return sorted(res)

Key components of the solution:

1. res list: Stores all valid paths found.
2. Edge Cases: Checks if the start or end cell is blocked. If so, returns an empty list immediately.
3. vis matrix: A 2D array of the same dimensions as the maze, used to mark cells that have been visited in the current path. This prevents revisiting cells within a single path.
4. dfs(i, j, path) function:
   • i, j: Current row and column coordinates of the rat.
   • path: The string representing the sequence of moves taken so far to reach (i, j).
   • Base Case: If (i, j) is the destination (n-1, n-1), the current path is a valid solution, so it’s added to res.
   • Mark Visited: Before exploring neighbors, the current cell (i, j) is marked as visited (vis[i][j] = 1).
   • Explore Neighbors: It checks all four possible directions (Down, Left, Right, Up) in a specific order to influence the lexicographical sorting later. For each direction, it verifies three conditions:
     • Is the move within maze bounds?
     • Has the cell already been visited in this path? (not vis[...])
     • Is the cell not blocked? (maze[...])
       If all conditions are met, a recursive dfs call is made for the new cell, appending the corresponding direction character to the path.
   • Backtrack: After exploring all possibilities from (i, j), the cell is unmarked (vis[i][j] = 0). This is crucial because (i, j) might be part of another valid path that is explored later.
5. Initial Call: The dfs function is initially called from (0, 0) with an empty path string.
6. Sorting: Finally, sorted(res) ensures that the paths are returned in lexicographically smallest order.

This problem beautifully illustrates how a recursive approach combined with careful state management (like the vis array for tracking visited cells) can systematically explore all possibilities in a search space. Mastering backtracking is essential for many algorithmic challenges.