Rat in a Maze — Backtracking Explained With Code and Intuition
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.
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).
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(); } } }
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
false false false false
false false false false
false false false false
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.
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(); } } }
Path found! Solution grid (1 = rat's path):
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1
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.
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; } }
DDRDD
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.
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]; } }
DDRDD
| 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 |
| 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.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Not backtracking the visited grid — The rat marks cells as visited but never unmarks them when retreating, so every dead end permanently closes off cells that future paths could use. 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.
- ✕Mistake 2: Checking boundaries after the recursive call instead of before — The function calls findPath(row+1, col) and then inside that call checks if row is out of bounds. This works logically, but it means you push a new stack frame just to immediately return false. With a dense, large maze this wastes stack space and can cause a StackOverflowError in extreme cases. Fix: move the boundary and validity check into an isValidMove() helper and call it BEFORE recursing, so invalid directions never get a stack frame.
- ✕Mistake 3: Forgetting to handle the case where the source cell [0][0] is itself a 0 — The recursive function's first action is usually to mark the cell as visited and proceed, skipping the check for whether the starting cell is passable. This means on a maze where maze[0][0] == 0, the rat gets placed on a wall and the function either crashes or returns a garbage path. 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.
Interview Questions on This Topic
- QHow would you modify the algorithm to find the shortest path through the maze, not just any valid path? (Answer involves switching from DFS/backtracking to BFS, since BFS explores layer by layer and guarantees the first path found is the shortest by number of steps.)
- QWhat's the difference between the visited array and the solution path array in your implementation, and why do you need both? (Tests whether the candidate understands that visited tracks the current exploration state and gets reset, while solutionPath records only confirmed valid routes — conflating them breaks either backtracking or the final output.)
- QIf the rat could also move diagonally (8 directions instead of 4), what exactly would you change in the code? (A strong answer demonstrates the direction-arrays pattern — you'd just extend rowDirections and colDirections with the four diagonal offsets and add their labels. A weak answer starts rewriting four if-blocks into eight, showing the candidate is writing code structurally rather than thinking about it.)
Frequently Asked Questions
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.
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.
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.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.