Rat in Maze Backtracking — Missing Visited Causes Loop
Robot logs repeat cell visits; OOM kills process.
20+ years shipping performance-critical code where algorithms decide the bill. Drawn from code that ran under real load.
- ✓Solid grasp of fundamentals
- ✓Comfortable reading code examples
- ✓Basic production concepts
- 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
The Rat in a Maze problem is a classic backtracking exercise where a rat must navigate from the top-left corner to the bottom-right corner of an N×N grid, moving only right or down through open cells (1s) while avoiding blocked cells (0s). It exists to teach the fundamental backtracking pattern: explore a path, mark your state, recurse, then unmark if it fails.
The problem is deceptively simple—missing the 'visited' marking causes infinite loops because the rat can revisit cells, creating cycles even in a directed grid. In practice, this mirrors real-world constraint satisfaction problems like Sudoku solvers, N-Queens, or pathfinding in robotics, where state tracking prevents redundant exploration.
Alternatives include BFS for shortest paths or Dijkstra for weighted grids, but backtracking is preferred when you need all solutions or when the search space is small enough to enumerate. Companies like Google and Amazon use variants in interviews to test recursive thinking and debugging skills—expect to handle both finding one path and collecting all paths, with complexity O(2^(n²)) in the worst case.
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.
Why Rat in Maze Is the Classic Backtracking Trap
The rat-in-maze problem asks: given an N×N grid with blocked cells, find a path from (0,0) to (N-1,N-1) moving only right or down. The core mechanic is backtracking — try a direction, recurse, and if it fails, undo the move and try the next. The naive recursive solution is O(2^(N*N)) in the worst case, but with pruning and visited tracking it drops to O(N^2).
The key property that matters in practice: the problem is a decision tree where each cell is a state. Without marking visited cells, the rat revisits the same cell, causing infinite loops or exponential blowup. The visited array is not an optimization — it’s a correctness requirement. The standard solution uses a boolean[][] visited that is set true on entry and false on backtrack.
Use this problem when teaching backtracking because it isolates the undo pattern without side effects. In real systems, the same pattern appears in constraint satisfaction (scheduling, routing) and state-space search (game AI, puzzle solvers). Understanding why missing visited causes a loop directly translates to avoiding infinite recursion in any recursive search.
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.
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(); } } }
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.
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(); } } }
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.
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; } }
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.
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]; } }
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.
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); } }
The Lexicographic Order Trap: Why Direction Order Matters
Competitors tell you to return paths in lexicographically sorted order. They don't tell you why your recursive solution explodes when you don't enforce it at the recursion level.
Here's the deal: the order in which you explore directions directly determines the order of results. If you explore U, D, L, R randomly, you'll get paths like "DDRDRR" and "DRDDRR" but in whatever order your stack feels like. Then you'll sort them after — and pay O(p log p) for something you could do for free.
The fix is boring and obvious once you see it: arrange your direction vectors in lexicographic order (D, L, R, U). This way, the recursive calls naturally generate paths in sorted order. No post-processing. No extra memory. Just a smarter enumeration strategy.
Most tutorials show you the sorted direction arrays but never explain why. The why matters when your interview runs long and you need to shave time.
// io.thecodeforge — dsa tutorial public class LexicographicPaths { // D, L, R, U — lexicographic order private static final int[] ROW_MOVES = {1, 0, 0, -1}; private static final int[] COL_MOVES = {0, -1, 1, 0}; private static final char[] DIRS = {'D', 'L', 'R', 'U'}; public List<String> findAllPaths(int[][] maze) { List<String> paths = new ArrayList<>(); boolean[][] visited = new boolean[maze.length][maze[0].length]; backtrack(maze, 0, 0, "", visited, paths); return paths; // Already in lexicographic order } private void backtrack(int[][] maze, int r, int c, String path, boolean[][] visited, List<String> paths) { int n = maze.length; if (r == n-1 && c == n-1) { paths.add(path); return; } visited[r][c] = true; for (int i = 0; i < 4; i++) { int nr = r + ROW_MOVES[i]; int nc = c + COL_MOVES[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1 && !visited[nr][nc]) { backtrack(maze, nr, nc, path + DIRS[i], visited, paths); } } visited[r][c] = false; // backtrack } }
The Grid-Copy Catastrophe: When Pass-by-Reference Bites You
Every junior writes backtracking like this: pass the visited matrix by reference, mutate it, then revert. Works fine until they need to explore all paths and accidentally share state across branches.
Here's the real problem: When you mark a cell visited, it's supposed to be local to that specific recursive path. But if you're not careful with where you unmark, you can block valid paths because another branch still thinks that cell is occupied. Classic off-by-one in recursion.
I've seen production code where engineers used a global visited matrix shared across multiple maze-solving threads. Chaos. Each call corrupted the other's state.
The fix? Either pass a copy (O(n²) per call — expensive but safe for small grids), or use the standard mark-before-descend, unmark-after-return pattern. The latter is what everyone uses, but they forget to unmark after ALL recursive calls, not just the successful ones. Use a try-finally block in Java, or ensure the unmark happens in the callee after exploring all directions.
Don't be that person who debugs for three hours because someone forgot a line of backtracking.
// io.thecodeforge — dsa tutorial public class BacktrackSafeMaze { public List<String> solve(int[][] maze) { List<String> results = new ArrayList<>(); boolean[][] visited = new boolean[maze.length][maze[0].length]; // Ensure start is open if (maze[0][0] == 0) return results; dfs(maze, 0, 0, "", visited, results); return results; } private void dfs(int[][] maze, int r, int c, String path, boolean[][] visited, List<String> results) { int n = maze.length; if (r == n-1 && c == n-1) { results.add(path); return; } visited[r][c] = true; // Mark int[] dr = {1, 0, 0, -1}; int[] dc = {0, -1, 1, 0}; char[] dir = {'D', 'L', 'R', 'U'}; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1 && !visited[nr][nc]) { dfs(maze, nr, nc, path + dir[i], visited, results); } } visited[r][c] = false; // Unmark — always happens } }
Why the Rat in Maze Is a Bad Proxy for Real-World Pathfinding
Every DSA course uses Rat in Maze to teach backtracking. Fine. But when you actually need to route packets through a network or navigate a robot through a warehouse, this algorithm will get you fired.
Here's why: The rat explores all paths. Exhaustive search. That's O(4^(n²)) — exponential in the worst case. For a 10x10 grid (100 cells), that's 4^100. The universe will end before your algorithm finishes.
Real pathfinding uses Dijkstra, A*, or at minimum BFS. Those give you the shortest path, often without exploring the entire state space. Rat in Maze gives you all paths, which is overkill when you just want one good route.
But here's where it does matter: constrained search spaces. If your grid is tiny (under 6x6), or you genuinely need to enumerate every alternative (like circuit board trace routing), backtracking is your hammer. Just don't bring a hammer to a neurosurgery.
The real lesson? Learn when to brute force and when to heuristic. Maze problems train pattern recognition for state-space search. Apply them to actual navigation and you'll grind production to a halt.
// io.thecodeforge — dsa tutorial public class MazeComparator { // This is a thought exercise, not runnable code public static void main(String[] args) { int[][] maze = { {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 0, 0}, {1, 1, 1, 1, 1} }; // Backtracking: finds 2 paths, takes ~2ms // BFS: finds shortest path (1 path), takes ~0.1ms // A* with heuristic: fastest, ~0.05ms System.out.println("Rat in Maze: enumerating all paths is a toy problem."); System.out.println("Real world: use A* and only find what you need."); } }
Infinite Recursion in Production Robot Navigation
- 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.
java -Xss256k -cp . RatInMazeSolverSystem.out.println("Entering (" + row + "," + col + ") depth=" + depth);if (currentRow == 0 && currentCol == 0) { System.out.println("Starting..."); }printMaze(maze); printVisited(visited);for (int[] row : solutionPath) { System.out.println(Arrays.toString(row)); }Add validation: after finishing, check each step's maze value.| 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 |
| File | Command / Code | Purpose |
|---|---|---|
| MazeSetup.java | public class MazeSetup { | Understanding the Grid |
| RatInMazeSolver.java | public class RatInMazeSolver { | The Backtracking Engine |
| RatInMazeAllPaths.java | public class RatInMazeAllPaths { | Finding All Valid Paths |
| RatInMazeOptimized.java | /** | Gotchas, Complexity, and How This Applies Beyond Mazes |
| BacktrackingDebugHelper.java | public class BacktrackingDebugHelper { | Debugging Recursive Backtracking |
| LexicographicPaths.java | public class LexicographicPaths { | The Lexicographic Order Trap |
| BacktrackSafeMaze.java | public class BacktrackSafeMaze { | The Grid-Copy Catastrophe |
| MazeComparator.java | public class MazeComparator { | Why the Rat in Maze Is a Bad Proxy for Real-World Pathfindin |
Key takeaways
Common mistakes to avoid
4 patternsNot backtracking the visited grid
Checking boundaries after the recursive call instead of before
Forgetting to handle the case where the source cell [0][0] is itself a 0
Using String concatenation for path building in all-paths mode
Practice These on LeetCode
Interview Questions on This Topic
How would you modify the algorithm to find the shortest path through the maze, not just any valid path?
What's the difference between the visited array and the solution path array in your implementation, and why do you need both?
If the rat could also move diagonally (8 directions instead of 4), what exactly would you change in the code?
What is the worst-case time complexity and why is it better in practice?
Frequently Asked Questions
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.
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.
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.
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.
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.
20+ years shipping performance-critical code where algorithms decide the bill. Drawn from code that ran under real load.
That's Greedy & Backtracking. Mark it forged?
8 min read · try the examples if you haven't