Rat in a Maze
Rat in a Maze: in an n×n grid of 0/1 cells, find all paths from (0,0) to (n−1,n−1) moving U/D/L/R through 1-cells, no cell reused.
- 2 <= n <= 5
- Grid cells are 0 (blocked) or 1 (open)
- No cell may be revisited within a single path
Intuition
Rat in a maze asks for every path from the top-left corner to the bottom-right of a grid, moving through open cells only and never reusing a cell. It is a pure backtracking problem: there is no formula for the answer, so you explore, and you undo what does not work. At each cell you face four choices — down, left, right, up. Some are immediately invalid: off the grid, blocked by a wall, or already part of the current path. The rest are worth exploring, and each one leads to the same decision repeated one cell further along. The no cell reused rule is what makes marking necessary. Without it the rat could step back and forth between two open cells forever. Marking a cell on entry and unmarking it on exit is the heart of backtracking: - Mark before recursing, unmark after — the cell is off-limits for this path, but must stay available to every other path. Forgetting the unmark is the classic bug. It does not crash; it silently loses valid paths, because cells consumed by one branch never become available to the next. One detail comes free if you order the moves carefully. Trying them as D, L, R, U — alphabetical order — means the resulting path strings come out already sorted, with no sort at the end.
Grid backtracking: mark the cell on entry so the path can't revisit itself, explore each direction, then unmark on the way out so other paths may use the cell. The unmark is what separates path enumeration from flood fill — a flood marks permanently because it only needs to visit once.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(4^(n²)) time and O(n²) space.
Reject the impossible start immediately
If the starting cell is blocked, no path exists and the answer is an empty list. Checking this once up front avoids a special case inside the recursion, where it would otherwise have to be handled on every call.
Try the four moves in D, L, R, U order
Iterate the directions in alphabetical order. Because the recursion explores them depth-first in that sequence, the collected paths emerge in lexicographic order for free — no sorting step at the end, which is what the problem expects.
Validate a move before recursing
A move is legal only if the target is inside the grid, is an open cell, and is not already on the current path. Testing all three before the recursive call keeps the search tree tight and avoids frames that would immediately return.
Mark, recurse, then unmark
Set the cell as visited before descending and clear it after returning. The grid itself can serve as the visited set — write a temporary blocking value and restore it afterwards. The unmark is not optional: without it, cells used by one path are permanently lost to every later one.
Record the path when the destination is reached
When the current cell is the bottom-right corner, the accumulated move string is a complete valid path — append a copy of it to the results. Then return so the caller can unmark and continue exploring alternatives.
Cost of the exhaustive search
With up to four choices per cell the search tree is O(4^(n²)) in the worst case, though walls and the visited marks prune it heavily in practice. Space is O(n²) for the recursion depth plus the space for the output, which can itself be exponential when the grid is wide open.
Solution & live demo
Common pitfalls
Not restoring the cell after exploring
maze[r][c] = 0
for ch, dr, dc in moves:
...maze[r][c] = 0
for ...:
...
maze[r][c] = 1 # unmarkCells stay blocked for every subsequent path, so only the first route is ever found. The mark exists to prevent revisiting within one path — once that path unwinds, the cell is available again.
Trying directions in an arbitrary order
moves = [("U",-1,0),("R",0,1),("D",1,0),("L",0,-1)]moves = [("D",1,0),("L",0,-1),("R",0,1),("U",-1,0)]GFG requires the paths in lexicographic order, and exploring in D-L-R-U order produces them sorted without a final sort. Any other order gives the same set of paths in the wrong sequence.
Not checking that the start or end is open
go(0, 0) return res
if not maze[0][0] or not maze[n-1][n-1]: return res
A blocked start would still be marked and explored from, and a blocked destination makes every search futile. Both guards are cheap and stop the recursion before it begins.
Edge cases
No path exists; return empty list.
Start is the destination — one path, the empty string.