Mid-level 7 min · March 06, 2026

Rat in Maze Backtracking — Missing Visited Causes Loop

Q: What is the time complexity of the Rat in a Maze problem?

The worst-case time complexity is O(4^(N²)), because at each of the N² cells the rat has at most 4 movement choices, and a path can theoretically visit all cells. In practice the visited constraint and walls prune the search tree dramatically, making the average case far faster. Space complexity is O(N²) for the recursion stack and auxiliary grids.

Q: Can the Rat in a Maze problem be solved without recursion?

Yes. You can use an explicit stack to simulate the recursion, implementing an iterative DFS. You push a cell onto the stack, mark it visited, explore neighbors, and pop + unmark when backtracking. However, the recursive version is almost always cleaner and easier to reason about, so it's preferred in interviews and educational contexts unless you're working in an environment with strict stack-size constraints.

Q: Why does the order of directions (D, L, R, U vs D, R, U, L) matter?

The order of exploration determines which path you find first and the lexicographic order of the output when printing all paths. Most online judges that ask you to 'print paths in lexicographic order' expect you to explore D before L before R before U, since D < L < R < U alphabetically. If your order is wrong, your logic may be perfectly correct but your output won't match the expected result — a frustrating bug to diagnose.

Q: How can I debug infinite recursion in backtracking?

Add a depth counter that increments on each recursive call. If depth exceeds N² + 1 (or a reasonable limit like 1000), throw a runtime exception with stack trace. Also add print statements at entry and exit to see which cells are being revisited. The most common cause is forgetting to unmark the visited array after backtracking.

Q: What real-world applications use backtracking?

Backtracking appears in constraint solvers (SMT solvers for formal verification), route planning in GPS (though usually with heuristics), robot pathfinding in unstructured environments, compiler parsing (recursive descent parsers), puzzle solvers (Sudoku, crosswords), and configuring resource allocation problems. Whenever you need to explore a decision space with pruning based on constraints, backtracking is a natural fit.

Robot logs repeat cell visits; OOM kills process.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

Backtracking explores paths one step at a time, retreating on dead ends
A visited grid prevents infinite loops and is the core 'undo' mechanism
Single-path mode returns early on success; all-paths mode fully explores the tree
Worst-case time is O(4^(N²)) but pruning makes real cases much faster
Biggest mistake: forgetting to unmark visited cells after backtracking

Plain-English First

Imagine you're inside a giant corn maze. You pick a path, walk forward, and hit a dead end. So you turn around, go back to the last fork, and try the next path. You keep doing this — go, hit a wall, come back, try something else — until you either find the exit or exhaust every option. That's backtracking in a nutshell. The 'rat in a maze' problem is just this exact idea, translated into a grid of cells where 1 means 'you can walk here' and 0 means 'wall — turn back'.

Most people assume that searching for a path through a maze is a simple loop problem. It isn't. A maze with multiple forks and dead ends creates a branching tree of decisions that can explode into millions of combinations. GPS systems, robot navigation, video game AI pathfinding, and even compiler token parsing all rely on the core idea behind this problem — the ability to explore possibilities, recognize a dead end early, and intelligently retreat to try something else.

The naive approach — trying every possible sequence of moves from start to end — would be catastrophically slow. Backtracking fixes this by pruning branches the moment they violate a rule. Instead of generating all paths and filtering afterward, you build a path one step at a time and abandon it the instant it becomes invalid. It's the difference between tasting every dish at a buffet and reading the menu first to skip what you know you'll hate.

By the end of this article you'll understand not just how to implement the Rat in a Maze problem in Java, but why backtracking works, when it outperforms other approaches, how to extend it to print all valid paths instead of just one, and exactly what interviewers are testing when they ask you about it. You'll walk away with a mental model you can apply to dozens of other problems — from N-Queens to Sudoku solvers.

Here's the thing: backtracking is a constraint satisfaction pattern. Every cell imposes three constraints — in bounds, not a wall, not visited. The algorithm doesn't guess and check; it checks before stepping. That shift — validating before diving instead of after — is what separates senior engineers from developers who write recursive code that just runs and crashes.

Understanding the Grid: Setting Up the Problem Correctly

Before writing a single line of code, you need to lock in the mental model. The maze is an N×N grid. Each cell holds either a 1 (passable) or a 0 (blocked). The rat starts at the top-left corner — cell [0][0] — and must reach the bottom-right corner — cell [N-1][N-1]. The rat can move in four directions: Up, Down, Left, Right.

The key constraint people miss early on is that you can't revisit a cell in the same path. Without this rule, the rat could loop between two open cells forever and your recursion would never terminate. To enforce it, you maintain a separate 'visited' grid — the same size as the maze — that tracks which cells are part of the current path being explored.

Think of the visited grid as leaving breadcrumbs. When you step into a cell, you drop a breadcrumb. If you hit a dead end, you pick the breadcrumb back up as you retreat. This is the 'undo' step that makes backtracking different from a plain recursive search. It keeps the state clean for the next attempt.

This setup also reveals the three conditions you must check before entering any cell: it must be inside the grid boundaries, it must be a 1 (not a wall), and it must not already be part of the current path (not visited).

One more nuance: the visited grid must be reset for each new exploration branch. That's why we unmark when backtracking. If you forget the undo, cells that lead to dead ends become permanently blocked and your algorithm will miss valid paths.

MazeSetup.javaJAVA

public class MazeSetup {

    public static void main(String[] args) {
        // A 4x4 maze: 1 = open path, 0 = wall
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        int size = maze.length;

        // Visited grid — same dimensions as the maze, all false by default
        // True means this cell is already on our current path
        boolean[][] visited = new boolean[size][size];

        // Print the initial state of the maze
        System.out.println("Maze layout (1=open, 0=wall):");
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                System.out.print(maze[row][col] + " ");
            }
            System.out.println();
        }

        // Confirm visited grid is clean before we start
        System.out.println("\nVisited grid (all false = clean slate):");
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                System.out.print(visited[row][col] + " ");
            }
            System.out.println();
        }
    }
}

Output

Maze layout (1=open, 0=wall):

1 0 0 0

1 1 0 1

0 1 0 0

1 1 1 1

Visited grid (all false = clean slate):

false false false false

Watch Out:

Many beginners skip the visited grid entirely and rely only on the maze's 0s and 1s to block movement. This works for some layouts, but the moment you have a loop in the open cells (two 1s that are mutually reachable), your recursion will cycle infinitely and blow the stack. Always use a separate visited grid.

Production Insight

In production robot navigation, a missing visited grid caused a 2-hour downtime at a warehouse.

The robot ping-ponged between two cells, draining its battery and locking up the control software.

Always treat the visited marker as a critical safety constraint, not an optimization.

Key Takeaway

The three conditions for a move: in bounds, not a wall, not visited.

Without the third, you have no loop protection.

Visited grid symmetry (mark before recurse, unmark after) is the soul of backtracking.

The Backtracking Engine: Finding One Valid Path

Now for the heart of the problem. Backtracking is a depth-first search with an undo mechanism. The recursive function does four things in order: check if the current cell is valid (boundary + not a wall + not visited), mark it as visited, check if we've reached the destination, recurse into all four neighbors, then — and this is the critical part — unmark the cell as visited before returning.

That last step is the soul of backtracking. By unmarking on the way back up, you ensure that a cell blocked in one failed path is free to be used in a completely different path. Without this undo, you'd permanently close off routes that might lead to valid solutions.

The recursion naturally forms a tree. Each node in that tree is a cell in the maze. Each branch is a direction you chose to move. When a branch hits a dead end — a wall, a boundary, or a revisited cell — the function returns false and the parent node tries its next branch. When a branch reaches the destination, it returns true and that success bubbles all the way up the call stack.

The solution path is tracked in a separate result grid that gets filled with 1s only when we know a cell is on a valid route to the exit. This is different from the visited grid, which tracks the current exploration attempt.

A common performance trap: the order of direction checks matters. The standard order (Down, Right, Up, Left) is arbitrary, but for all-paths lexicographic output you must follow D, L, R, U. Also, checking boundaries after the recursive call adds unnecessary stack frames — always validate before recursing.

RatInMazeSolver.javaJAVA

100

101

102

103

104

public class RatInMazeSolver {

    static int MAZE_SIZE;

    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        MAZE_SIZE = maze.length;

        // This grid will record the final valid path (1 = on the path, 0 = not)
        int[][] solutionPath = new int[MAZE_SIZE][MAZE_SIZE];

        // Separate visited tracker to prevent revisiting cells in the same path
        boolean[][] visited = new boolean[MAZE_SIZE][MAZE_SIZE];

        System.out.println("Searching for a path from [0][0] to [" + (MAZE_SIZE-1) + "][" + (MAZE_SIZE-1) + "]...\n");

        if (findPath(maze, 0, 0, solutionPath, visited)) {
            System.out.println("Path found! Solution grid (1 = rat's path):");
            printGrid(solutionPath);
        } else {
            System.out.println("No path exists from start to destination.");
        }
    }

    /**
     * Recursively explores the maze using backtracking.
     * Returns true if a path to the destination exists from (currentRow, currentCol).
     */
    static boolean findPath(int[][] maze, int currentRow, int currentCol,
                            int[][] solutionPath, boolean[][] visited) {

        // --- BASE CASE CHECKS (the 'prune' step) ---

        // 1. Out of bounds — stepped outside the grid
        if (currentRow < 0 || currentRow >= MAZE_SIZE ||
            currentCol < 0 || currentCol >= MAZE_SIZE) {
            return false;
        }

        // 2. Cell is a wall — can't pass through
        if (maze[currentRow][currentCol] == 0) {
            return false;
        }

        // 3. Already visited in this path — would create a loop
        if (visited[currentRow][currentCol]) {
            return false;
        }

        // --- MARK THIS CELL AS PART OF THE CURRENT PATH ---
        visited[currentRow][currentCol] = true;
        solutionPath[currentRow][currentCol] = 1; // tentatively add to solution

        // --- SUCCESS CASE: We've reached the destination ---
        if (currentRow == MAZE_SIZE - 1 && currentCol == MAZE_SIZE - 1) {
            return true; // Don't backtrack — this path is valid!
        }

        // --- EXPLORE ALL FOUR DIRECTIONS ---
        // Order: Down, Right, Up, Left (common convention)

        // Move Down
        if (findPath(maze, currentRow + 1, currentCol, solutionPath, visited)) {
            return true;
        }

        // Move Right
        if (findPath(maze, currentRow, currentCol + 1, solutionPath, visited)) {
            return true;
        }

        // Move Up
        if (findPath(maze, currentRow - 1, currentCol, solutionPath, visited)) {
            return true;
        }

        // Move Left
        if (findPath(maze, currentRow, currentCol - 1, solutionPath, visited)) {
            return true;
        }

        // --- BACKTRACK: None of the directions worked from here ---
        // Undo this cell — remove the breadcrumb
        visited[currentRow][currentCol] = false;
        solutionPath[currentRow][currentCol] = 0; // remove from solution path

        return false; // signal failure to the parent call
    }

    static void printGrid(int[][] grid) {
        for (int[] row : grid) {
            for (int cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}

Output

Searching for a path from [0][0] to [3][3]...

Path found! Solution grid (1 = rat's path):

1 0 0 0

1 1 0 0

0 1 0 0

0 1 1 1

Pro Tip:

Notice that when we reach the destination we return true immediately WITHOUT backtracking. The solutionPath grid keeps those 1s intact. If you accidentally add backtracking logic after the success check (like setting solutionPath to 0 unconditionally on return), you'll erase your own answer. The undo step should only run when all four directions have failed.

Production Insight

Single-path mode is great for solvability checks (e.g., is there a way for the robot to reach the charger?).

In production, a common mistake is calling the recursive function without the initial start cell check, causing it to fail silently.

Always guard: if (maze[0][0] == 1) { findPath(...); } else { no path; }

Key Takeaway

Recursion returns true only when destination is reached.

All dead ends return false, triggering backtrack on the parent.

The undo step (unmark visited AND clear solution) only runs after all children fail.

Finding All Valid Paths — The Real Interview Question

Returning one valid path is the warm-up. The real interview challenge is: 'Print every valid path from start to destination.' This changes the algorithm in a subtle but important way.

When you find the destination, instead of returning true immediately and stopping, you record the current path, then continue backtracking to explore remaining branches. This means you never short-circuit on success — you always unmark the cell and return, allowing other paths to be discovered.

The path itself is recorded as a string of direction characters — 'D' for Down, 'R' for Right, 'U' for Up, 'L' for Left — built up as you recurse deeper and trimmed as you backtrack. This is more elegant than copying the entire grid at each step and far cheaper on memory.

This variant is also where the ordering of your direction exploration matters for the lexicographic ordering of output. Most interview problems that specify 'print paths in lexicographic order' expect you to try Down before Left before Right before Up (D, L, R, U alphabetically), which is a small but test-critical detail many candidates miss.

Also note: in the all-paths version, you never need the solutionPath grid. You only track the current path as a string or StringBuilder. That simplifies the code and reduces memory overhead.

RatInMazeAllPaths.javaJAVA

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

public class RatInMazeAllPaths {

    static int MAZE_SIZE;

    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        MAZE_SIZE = maze.length;
        List<String> allValidPaths = new ArrayList<>();
        boolean[][] visited = new boolean[MAZE_SIZE][MAZE_SIZE];

        // Only start if the source cell itself is open
        if (maze[0][0] == 1) {
            collectAllPaths(maze, 0, 0, "", visited, allValidPaths);
        }

        if (allValidPaths.isEmpty()) {
            System.out.println("No valid paths exist.");
        } else {
            System.out.println("All valid paths (" + allValidPaths.size() + " found):");
            for (String path : allValidPaths) {
                System.out.println(path);
            }
        }
    }

    /**
     * Explores all paths using backtracking.
     * Unlike single-path mode, we never short-circuit — we always backtrack
     * after recording a solution so we can find more.
     *
     * @param currentPath  String built up character by character representing moves
     */
    static void collectAllPaths(int[][] maze, int currentRow, int currentCol,
                                String currentPath, boolean[][] visited,
                                List<String> allValidPaths) {

        // Guard: out of bounds
        if (currentRow < 0 || currentRow >= MAZE_SIZE ||
            currentCol < 0 || currentCol >= MAZE_SIZE) {
            return;
        }

        // Guard: wall or already visited in this path
        if (maze[currentRow][currentCol] == 0 || visited[currentRow][currentCol]) {
            return;
        }

        // SUCCESS: destination reached — record this path and THEN backtrack
        if (currentRow == MAZE_SIZE - 1 && currentCol == MAZE_SIZE - 1) {
            allValidPaths.add(currentPath); // save the completed path
            return; // backtrack to look for more paths (no early exit!)
        }

        // Mark current cell as visited for this exploration branch
        visited[currentRow][currentCol] = true;

        // Explore in lexicographic order: D, L, R, U
        // This ensures results come out alphabetically sorted
        collectAllPaths(maze, currentRow + 1, currentCol, currentPath + "D", visited, allValidPaths); // Down
        collectAllPaths(maze, currentRow, currentCol - 1, currentPath + "L", visited, allValidPaths); // Left
        collectAllPaths(maze, currentRow, currentCol + 1, currentPath + "R", visited, allValidPaths); // Right
        collectAllPaths(maze, currentRow - 1, currentCol, currentPath + "U", visited, allValidPaths); // Up

        // BACKTRACK: unmark so other paths can use this cell
        visited[currentRow][currentCol] = false;
    }
}

Output

All valid paths (1 found):

DDRDD

Interview Gold:

The single most common follow-up question after this problem is: 'What's the time complexity?' The answer is O(4^(N²)) in the worst case — at every cell you have at most 4 choices, and the path can be at most N² cells long. In practice it's far better because walls and the visited constraint prune the search tree aggressively. Saying this out loud in an interview shows you understand backtracking's real-world efficiency, not just its worst-case bound.

Production Insight

If you need to evaluate which path is optimal (shortest, safest), all-paths backtracking is rarely the right tool.

For shortest path, switch to BFS — backtracking enumerates all routes even when you only need the best.

But for compliance audits where you must present all possible routes, backtracking is the go-to.

Key Takeaway

All-paths = record, don't return early.

Single-path = return true on first success.

Everything else (visited management, pruning) stays exactly the same.

Gotchas, Complexity, and How This Applies Beyond Mazes

The Rat in a Maze problem is a teaching vehicle for a pattern you'll use repeatedly: constraint-based recursive exploration with state restoration. Once you internalize this pattern, Sudoku solvers, the N-Queens problem, word search in a grid, and generating valid parentheses all become variations on the same theme.

The time complexity is O(4^(N²)) worst case since each cell can branch four ways and paths can span the full grid. Space complexity is O(N²) for the recursion call stack (depth equals the longest path) plus the visited and solution grids.

One architectural decision worth knowing: using a String to accumulate the path (currentPath + "D") creates a new String object at every recursive call because Java Strings are immutable. For very large mazes this generates significant garbage. A StringBuilder passed by reference and manually appended/deleted is more efficient. The append/deleteCharAt(sb.length()-1) pattern is the StringBuilder equivalent of the visited array's mark/unmark dance.

This problem also demonstrates why backtracking is classified under constraint satisfaction problems (CSPs). The constraints — stay in bounds, avoid walls, don't revisit — define the valid solution space. Backtracking explores that space efficiently by checking constraints before going deeper, not after.

Another subtle gotcha: when the start or end cell is a wall, the algorithm should immediately report no path. Most implementations miss this check for the start cell, causing the recursive function to enter a wall and return false but the outer code may still print 'path found' incorrectly. Always guard at the top.

RatInMazeOptimized.javaJAVA

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

/**
 * Optimized version using StringBuilder instead of String concatenation.
 * Avoids creating a new String object at every recursive call.
 * Important for large mazes where path length can be significant.
 */
public class RatInMazeOptimized {

    static int MAZE_SIZE;

    // Direction arrays keep the code clean and easy to extend
    // Order: D, L, R, U — lexicographic for sorted output
    static int[] rowDirections = {1, 0,  0, -1};
    static int[] colDirections = {0, -1, 1,  0};
    static char[] directionLabels = {'D', 'L', 'R', 'U'};

    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        MAZE_SIZE = maze.length;
        List<String> allPaths = new ArrayList<>();
        boolean[][] visited = new boolean[MAZE_SIZE][MAZE_SIZE];

        if (maze[0][0] == 1) {
            // StringBuilder mutated in place — much cheaper than String + String
            StringBuilder pathBuilder = new StringBuilder();
            collectPaths(maze, 0, 0, pathBuilder, visited, allPaths);
        }

        System.out.println("Valid paths found: " + allPaths.size());
        allPaths.forEach(System.out::println);
    }

    static void collectPaths(int[][] maze, int row, int col,
                             StringBuilder pathBuilder, boolean[][] visited,
                             List<String> allPaths) {

        // Destination reached — snapshot the path and backtrack
        if (row == MAZE_SIZE - 1 && col == MAZE_SIZE - 1) {
            allPaths.add(pathBuilder.toString()); // snapshot, not reference
            return;
        }

        visited[row][col] = true; // mark before exploring neighbors

        // Loop over all 4 directions using the direction arrays
        for (int direction = 0; direction < 4; direction++) {
            int nextRow = row + rowDirections[direction];
            int nextCol = col + colDirections[direction];

            // Check validity before recursing — this IS the pruning
            if (isValidMove(maze, nextRow, nextCol, visited)) {
                pathBuilder.append(directionLabels[direction]); // build path
                collectPaths(maze, nextRow, nextCol, pathBuilder, visited, allPaths);
                pathBuilder.deleteCharAt(pathBuilder.length() - 1); // undo path character
            }
        }

        visited[row][col] = false; // unmark — restore state for other branches
    }

    static boolean isValidMove(int[][] maze, int row, int col, boolean[][] visited) {
        return row >= 0 && row < MAZE_SIZE &&
               col >= 0 && col < MAZE_SIZE &&
               maze[row][col] == 1 &&
               !visited[row][col];
    }
}

Output

Valid paths found: 1

DDRDD

Pro Tip:

The direction arrays pattern (rowDirections, colDirections, directionLabels) is a professional habit worth adopting immediately. Instead of four separate if-blocks for Up/Down/Left/Right, you loop over four indices. Adding diagonal movement later becomes trivial — just extend the arrays. It also makes your intent immediately readable to any reviewer.

Production Insight

In a production pathfinding system for a 100x100 warehouse grid, String concatenation caused GC pauses of 200ms every few seconds.

Switching to StringBuilder eliminated the pauses entirely.

Always use StringBuilder when building paths recursively in Java.

Key Takeaway

Complexity: O(4^(N²)) time, O(N²) space.

String concatenation is expensive — use StringBuilder.

The pattern generalizes: every CSP with recursive state restoration follows this skeleton.

Debugging Recursive Backtracking: A Practical Guide

Backtracking code is notoriously hard to debug because the call stack is deep and the state changes rapidly. The two most common bugs are forgetting to unmark visited cells and accidentally returning early in all-paths mode. Here's a systematic approach to debugging that will save you hours.

First, add a depth counter and print coordinates at each entry and exit. This lets you see the recursion tree and spot loops immediately. For example: System.out.println("Enter ("+row+","+col+") depth="+depth); at the top, and the same at the bottom. If you see the same coordinate at the same depth multiple times, you have an unmark bug.

Second, use a small maze (2x2 or 3x3) where you know the expected paths. This minimizes variable space and makes it easy to trace manually.

Third, separate the logic into clearly named methods: isValidMove(), mark(), unmark(). That way you can verify each piece independently. The mark/unmark symmetry is the most critical mental check.

Fourth, for infinite recursion, add a maximum depth guard. If depth exceeds N²+1, throw an exception with a clear message. This catches loops early and prevents stack overflow from hiding the real bug.

Finally, test edge cases: maze with no walls (all 1s), maze with start blocked (maze[0][0]==0), maze with only a single path, and maze with diagonal open spaces that form loops.

BacktrackingDebugHelper.javaJAVA

public class BacktrackingDebugHelper {

    static int MAZE_SIZE;
    static final int MAX_DEPTH = 100; // safety limit

    public static void main(String[] args) {
        // Use a small 2x2 maze for debugging
        int[][] maze = {
            {1, 1},
            {1, 1}
        };
        MAZE_SIZE = maze.length;
        boolean[][] visited = new boolean[MAZE_SIZE][MAZE_SIZE];
        StringBuilder path = new StringBuilder();
        
        if (maze[0][0] == 1) {
            explore(maze, 0, 0, path, visited, 0);
        } else {
            System.out.println("Start cell blocked!");
        }
    }

    static void explore(int[][] maze, int row, int col,
                        StringBuilder path, boolean[][] visited, int depth) {
        // Depth guard to catch infinite recursion
        if (depth > MAX_DEPTH) {
            throw new RuntimeException("Max depth exceeded - likely infinite recursion!");
        }

        System.out.println("Enter (" + row + "," + col + ") depth=" + depth);

        if (row < 0 || row >= MAZE_SIZE || col < 0 || col >= MAZE_SIZE) {
            System.out.println("  Out of bounds -> backtrack");
            return;
        }
        if (maze[row][col] == 0) {
            System.out.println("  Wall -> backtrack");
            return;
        }
        if (visited[row][col]) {
            System.out.println("  Already visited -> backtrack");
            return;
        }

        // Mark
        visited[row][col] = true;

        if (row == MAZE_SIZE-1 && col == MAZE_SIZE-1) {
            System.out.println("  REACHED DESTINATION! Path so far: " + path.toString());
            // In all-paths mode, record and continue; in single-path, return here
        }

        // Recurse in all four directions
        explore(maze, row+1, col, path.append('D'), visited, depth+1);
        path.deleteCharAt(path.length()-1);

        explore(maze, row, col-1, path.append('L'), visited, depth+1);
        path.deleteCharAt(path.length()-1);

        explore(maze, row, col+1, path.append('R'), visited, depth+1);
        path.deleteCharAt(path.length()-1);

        explore(maze, row-1, col, path.append('U'), visited, depth+1);
        path.deleteCharAt(path.length()-1);

        // Unmark
        visited[row][col] = false;
        System.out.println("Exit (" + row + "," + col + ") depth=" + depth);
    }
}

Output

Enter (0,0) depth=0

Enter (1,0) depth=1

Enter (1,-1) depth=2

Out of bounds -> backtrack

Enter (1,0) depth=2

Already visited -> backtrack

Enter (1,1) depth=2

REACHED DESTINATION! Path so far: DR

Enter (2,1) depth=3

Out of bounds -> backtrack

... (continues)

Debugging Trap:

Adding System.out.println inside a recursive backtracking function can flood your console. Use a depth counter and print only at critical steps (entry, exit, success). Or use a logger with a conditional check on depth. In production, log at debug level and tag each message with the recursion branch ID.

Production Insight

In a real incident, a pathfinding bug caused a robot to navigate into a corner and stall for 30 minutes.

The debug logs showed the robot entering the same cell 500 times at increasing depths.

Always add a depth guard in production code — it turns a silent loop into an actionable alert.

Key Takeaway

Add depth guard and entry/exit logging during development.

Test with the smallest possible maze (2x2 all 1s) to verify mark/unmark symmetry.

In production, remove print statements — but keep the depth guard as a safety net.

● Production incidentPOST-MORTEMseverity: high

Infinite Recursion in Production Robot Navigation

Symptom

Robot logs showed repeated entries for the same cell coordinates every few milliseconds. Memory usage spiked then the process was killed by OOM killer. Destination never reached.

Assumption

The developer assumed the maze's wall marker (0) was enough to block revisits. They thought the recursion would naturally stop because the robot's path would hit a wall eventually.

Root cause

No visited grid. The backtracking function checked only walls, not whether the current cell had already been visited in the current path. When two adjacent cells were both open (1), the rat could move left then right forever. The recursion never terminated because each call made two more calls to the same cells.

Fix

Add a boolean visited array that is set to true when entering a cell and set back to false when backtracking. Check visited along with maze value before recursing. This breaks the loop.

Key lesson

Visited tracking is not optional — it's the only mechanism that prevents infinite cycles in open spaces.
Never assume the domain constraints (walls) are enough to prune all invalid branches.
Always pair mark and unmark: visited[row][col] = true before recursion, and visited[row][col] = false after all children return.
When debugging infinite recursion, add a depth counter or print coordinates to detect loops early.

Production debug guideSymptom → Action guide for the 3 most common backtracking failures4 entries

Symptom · 01

Algorithm never finishes (infinite loop) for mazes with open paths

→

Fix

Check if visited array is being reset after backtracking. Add print statements at entry and exit of recursive function to see if cells are being revisited without being unmarked.

Symptom · 02

StackOverflowError on moderately sized maze (e.g., 6x6)

→

Fix

Verify the base case checks are inside the recursive function, not only before the recursive call. Also ensure visited array prevents re-entering cells. Increase JVM stack size with -Xss if needed, but fix the algorithmic bug first.

Symptom · 03

Only one path found when multiple paths exist

→

Fix

Check if the function returns true immediately on reaching destination without continuing exploration. For all-paths mode, do NOT return after recording — you must backtrack even after success.

Symptom · 04

Path output contains invalid steps (e.g., moves through walls)

→

Fix

Ensure the isValidMove or boundary check is applied before marking visited, not after. Also verify that the solution path array is only written when the cell is confirmed valid.

★ Quick Debug Cheatsheet for Recursive BacktrackingUse these commands and steps when your backtracking implementation misbehaves at runtime.

Infinite recursion suspected−

Immediate action

Kill the process (Ctrl+C). Add a recursion depth counter and print on entry.

Commands

java -Xss256k -cp . RatInMazeSolver

System.out.println("Entering (" + row + "," + col + ") depth=" + depth);

Fix now

Ensure visited[row][col] = false is called AFTER all recursive calls return, not inside the base case.

No path found but a path exists+

Wrong path printed (includes walls)+

Single Path vs All Paths: Key Differences

Aspect	Find ONE Path (Return true/false)	Find ALL Paths (Collect all routes)
Goal	Confirm path exists + show one route	Enumerate every valid route
On reaching destination	Return true immediately — stop exploring	Record path, then return to keep exploring
Backtrack after success?	No — winning path stays marked	Yes — must undo to find remaining paths
Path storage	int[][] solutionPath grid	List<String> of direction sequences
Performance	Faster — exits on first success	Slower — exhausts entire search space
Use case	Maze solvability check, robot routing	Finding optimal route among valid ones
Complexity (time)	O(4^(N²)) worst case, exits early	O(4^(N²)) always explores fully
String vs StringBuilder	Not applicable	StringBuilder saves memory for large N

Key takeaways

Backtracking = DFS + undo

the visited array must be marked before recursing and unmarked after — this symmetry is what makes the algorithm correct, and forgetting the unmark is the single most common bug.

Finding one path vs. all paths changes only ONE thing

whether you return immediately on reaching the destination (one path) or record and continue (all paths). The rest of the algorithm is identical.

The direction-arrays pattern (rowDirections[], colDirections[]) replaces repetitive if/else blocks and makes adding diagonal movement or changing direction order a two-line change instead of a full rewrite.

Rat in a Maze is a gateway problem

the same backtracking skeleton — validate, mark, recurse, unmark — solves N-Queens, Sudoku, word search, and knight's tour. Master the pattern here and those problems become variations, not new challenges.

Always guard for blocked start cell and add a depth limit in production to prevent infinite recursion from silent stack overflow.

Use StringBuilder for path building in Java to avoid GC pressure from immutable String objects.

Common mistakes to avoid

4 patterns

Not backtracking the visited grid

Symptom

The algorithm reports no path even when one clearly exists, or only finds a small fraction of valid paths.

Fix

Always pair visited[row][col] = true with visited[row][col] = false after all recursive calls return, not just when you find a dead end.

Checking boundaries after the recursive call instead of before

Symptom

StackOverflowError on moderately sized mazes because too many frames are pushed.

Fix

Move the boundary and validity check into an isValidMove() helper and call it BEFORE recursing, so invalid directions never get a stack frame.

Forgetting to handle the case where the source cell [0][0] is itself a 0

Symptom

The function crashes or returns a garbage path when the starting cell is a wall.

Fix

Add an explicit guard before calling the recursive function — if (maze[0][0] == 1) { findPath(...) } — and treat the starting cell like any other cell in the validity check.

Using String concatenation for path building in all-paths mode

Symptom

Excessive GC pauses and slower execution on large mazes.

Fix

Switch to StringBuilder passed by reference. Append on entry, delete last character on backtrack.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

How would you modify the algorithm to find the shortest path through the...

Q02SENIOR

What's the difference between the visited array and the solution path ar...

Q03SENIOR

If the rat could also move diagonally (8 directions instead of 4), what ...

Q04SENIOR

What is the worst-case time complexity and why is it better in practice?

Q01 of 04SENIOR

How would you modify the algorithm to find the shortest path through the maze, not just any valid path?

ANSWER

Switch from DFS/backtracking to BFS, because BFS explores layer by layer and guarantees the first path found is the shortest by number of steps. Backtracking (DFS) finds some path, not necessarily the shortest. If the maze has unit weights per step, BFS is O(V+E) with O(V) space for the queue and visited set. If there are varying move costs, use Dijkstra or A*.

FAQ · 5 QUESTIONS

Frequently Asked Questions

What is the time complexity of the Rat in a Maze problem?

Can the Rat in a Maze problem be solved without recursion?

Why does the order of directions (D, L, R, U vs D, R, U, L) matter?

How can I debug infinite recursion in backtracking?

What real-world applications use backtracking?

🔥

That's Greedy & Backtracking. Mark it forged?

7 min read · try the examples if you haven't