Rat in a Maze

A rat starts at the top-left of an N×N maze and must reach the bottom-right. Cells with 1 are open; 0 are blocked. Find all paths using backtracking: try moves Down, Left, Right, Up (D, L, R, U), mark cells visited, and undo on backtrack. This lesson covers the algorithm and implementations in C, Java, and Python with trace tables.

Overview

Grid pathfinding with backtracking explores every valid route from source to destination. Each step appends a direction letter to the path string; visiting the same cell twice is forbidden, so we maintain a visited matrix.

4×4 maze (1 = open, 0 = wall)     S = start, E = end

  1 0 0 0                           S . . .
  1 1 0 1         →                 ↓ ↓   .
  0 1 0 0                           . ↓   .
  0 1 1 1                           . ↓ → E

Backtrack: mark visited → try D/L/R/U → unmark on return

Problem Statement

Input: N×N matrix maze where maze[i][j] ∈ {0, 1}.

Output: All path strings from (0, 0) to (N−1, N−1) using moves D, L, R, U. Return -1 or empty if no path exists.

Constraints:

• Start cell maze[0][0] and destination maze[N−1][N−1] must be 1.
• Rat cannot visit the same cell twice on one path.
• Only four-directional moves (no diagonals unless variant says so).

Backtracking Algorithm

1. If (row, col) is destination, record current path string and return.
2. Mark visited[row][col] = true.
3. For each direction in order (D, L, R, U):
   • Compute next cell (nr, nc) = (row + dr, col + dc).
   • If move is valid (in bounds, open, unvisited), append direction to path.
   • Recurse on (nr, nc).
   • Backtrack: remove last direction from path.
4. Unmark visited[row][col] = false before returning.

Move Pruning Rules

A move to (nr, nc) is allowed only when:

• In bounds: 0 ≤ nr, nc < N
• Open cell: maze[nr][nc] == 1
• Not visited: visited[nr][nc] == false

Code (C, Java, Python)

Python

def rat_in_maze(maze):
    """All paths from (0,0) to (n-1,n-1) — backtracking with visited[]."""
    n = len(maze)
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return []
    visited = [[False] * n for _ in range(n)]
    path = []
    result = []
    moves = "DLRU"
    dr = [1, 0, 0, -1]
    dc = [0, -1, 1, 0]

    def is_safe(row, col):
        return (0 <= row < n and 0 <= col < n
                and maze[row][col] == 1 and not visited[row][col])

    def backtrack(row, col):
        if row == n - 1 and col == n - 1:
            result.append("".join(path))
            return
        visited[row][col] = True
        for k in range(4):
            nr, nc = row + dr[k], col + dc[k]
            if not is_safe(nr, nc):
                continue
            path.append(moves[k])
            backtrack(nr, nc)
            path.pop()
        visited[row][col] = False

    backtrack(0, 0)
    return result


if __name__ == "__main__":
    grid = [
        [1, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 1, 0, 0],
        [0, 1, 1, 1],
    ]
    print(rat_in_maze(grid))  # ['DRDDRR']

Java

import java.util.ArrayList;
import java.util.List;

public class RatInMaze {

    private static final String MOVES = "DLRU";
    private static final int[] DR = {1, 0, 0, -1};
    private static final int[] DC = {0, -1, 1, 0};

    private static boolean isSafe(int[][] maze, boolean[][] visited, int row, int col) {
        int n = maze.length;
        return row >= 0 && row < n && col >= 0 && col < n
                && maze[row][col] == 1 && !visited[row][col];
    }

    public static void solve(int[][] maze, int row, int col, boolean[][] visited,
                             StringBuilder path, List<String> result) {
        int n = maze.length;
        if (row == n - 1 && col == n - 1) {
            result.add(path.toString());
            return;
        }
        visited[row][col] = true;
        for (int k = 0; k < 4; k++) {
            int nr = row + DR[k], nc = col + DC[k];
            if (!isSafe(maze, visited, nr, nc)) continue;
            path.append(MOVES.charAt(k));
            solve(maze, nr, nc, visited, path, result);
            path.deleteCharAt(path.length() - 1);
        }
        visited[row][col] = false;
    }

    public static List<String> ratInMaze(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return result;
        solve(maze, 0, 0, new boolean[n][n], new StringBuilder(), result);
        return result;
    }
}

C

#include <stdio.h>
#include <string.h>

char moves[] = "DLRU";
int dr[] = {1, 0, 0, -1};
int dc[] = {0, -1, 1, 0};

int is_safe(int maze[][10], int visited[][10], int n, int row, int col) {
    return row >= 0 && row < n && col >= 0 && col < n
        && maze[row][col] == 1 && !visited[row][col];
}

void rat_maze(int maze[][10], int visited[][10], int n,
              int row, int col, char path[], int depth, int *count) {
    int k, nr, nc;
    if (row == n - 1 && col == n - 1) {
        path[depth] = '\0';
        (*count)++;
        return;
    }
    visited[row][col] = 1;
    for (k = 0; k < 4; k++) {
        nr = row + dr[k];
        nc = col + dc[k];
        if (!is_safe(maze, visited, n, nr, nc)) continue;
        path[depth] = moves[k];
        rat_maze(maze, visited, n, nr, nc, path, depth + 1, count);
    }
    visited[row][col] = 0;
}

Output & Trace

Sample maze (4×4)

maze:
1 0 0 0
1 1 0 1
0 1 0 0
0 1 1 1

Path found (this maze has exactly 1 solution)

Partial trace — first few steps

Problem Variants

Optimizations

• Early exit: Return after first path if only one solution needed.
• BFS for shortest: Use queue when minimum steps matter.
• Bitmask visited: Compact state for small N in competitive programming.
• Dead-end marking: Advanced pruning — mark cells that cannot reach destination (rare in basic version).

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify: all paths vs one path vs shortest path.
2. Check start and end cells are open before recursing.
3. Mark visited on entry, unmark on exit — classic backtrack undo.
4. Use direction arrays dr[], dc[] to avoid repetitive code.
5. State complexity: exponential time, O(N²) space for visited.
6. Connect to word search (grid + visited) and Sudoku (constraint grid).