DSA Tracker

Visualize

Rat in a Maze

Path backtracking with a visited set, moves tried in D, L, R, U order

time O(4^(n^2))space O(n^2)

Four-directional movement means the rat can wander back toward cells it already stood on, so a plain grid walk can loop forever. Marking the current cell visited before stepping to a neighbor, and unmarking it the moment the recursion returns, blocks that cycle on the current branch while still letting a different branch pass through the same cell later. Moves are tried in a fixed alphabetical order (D, L, R, U) so the collected paths come out in a defined order. Reaching (n-1, n-1) records a path but does not stop the search — every other untried direction, at every depth, still gets explored.

Details

Animated on: n = 3, maze = [[1,0,0],[1,1,0],[1,1,1]]. Find every path from (0,0) to (n-1,n-1) moving D/L/R/U through open (1) cells, never revisiting a cell on the same path. Answer: ["DDRR","DRDR"].

Problem:Rat in a MazeMedium

Path backtracking with a visited set, moves tried in D, L, R, U order

step 1 / 15

(0, 0)
[0]

n = 3. (0, 0) is open, so the rat starts there. Directions are tried in alphabetical order D, L, R, U; a move is legal only if it stays in bounds, the cell is open (1) and not already on the current path.

  • at=0· arr[0] = (0, 0)
Pseudocode
1FUNCTION solveMaze(maze)
2  out <- EMPTY LIST
3  path <- EMPTY LIST
4  FUNCTION place(r, c)
5    IF (r, c) = (n - 1, n - 1)
6      APPEND JOIN(path) TO out
7      RETURN
8    FOR EACH (dir, dr, dc) IN [D, L, R, U]
9      IF NOT INBOUNDS(r+dr, c+dc) OR maze[r+dr][c+dc] = 0 OR visited[r+dr][c+dc]
10        CONTINUE
11      MARK visited[r+dr][c+dc], APPEND dir TO path
12      place(r+dr, c+dc)
13      REMOVE LAST FROM path, UNMARK visited[r+dr][c+dc]
14  place(0, 0)
15  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. n = 3. (0, 0) is open, so the rat starts there. Directions are tried in alphabetical order D, L, R, U; a move is legal only if it stays in bounds, the cell is open (1) and not already on the current path.
  2. From (0, 0), 'D' to (1, 0) is open and unvisited, so it is marked visited and appended to the path: "D".
  3. From (1, 0), 'D' to (2, 0) is open and unvisited, so it is marked visited and appended to the path: "DD".
  4. From (2, 0), 'R' to (2, 1) is open and unvisited, so it is marked visited and appended to the path: "DDR".
  5. From (2, 1), 'R' to (2, 2) is open and unvisited, so it is marked visited and appended to the path: "DDRR".
  6. (2, 2) is the destination (2, 2): path "DDRR" is solution #1. The search does not stop here — it backtracks and keeps trying the remaining directions from every cell already on the path.
  7. From (2, 1), 'U' to (1, 1) is open and unvisited, so it is marked visited and appended to the path: "DDRU".
  8. (1, 1) has no open, unvisited neighbor in any of D, L, R, U: this branch is a dead end. Backtrack — unmark it and let the cell below in the recursion try its next direction.
  9. From (1, 0), 'R' to (1, 1) is open and unvisited, so it is marked visited and appended to the path: "DR".
  10. From (1, 1), 'D' to (2, 1) is open and unvisited, so it is marked visited and appended to the path: "DRD".
  11. From (2, 1), 'L' to (2, 0) is open and unvisited, so it is marked visited and appended to the path: "DRDL".
  12. (2, 0) has no open, unvisited neighbor in any of D, L, R, U: this branch is a dead end. Backtrack — unmark it and let the cell below in the recursion try its next direction.
  13. From (2, 1), 'R' to (2, 2) is open and unvisited, so it is marked visited and appended to the path: "DRDR".
  14. (2, 2) is the destination (2, 2): path "DRDR" is solution #2. The search does not stop here — it backtracks and keeps trying the remaining directions from every cell already on the path.
  15. Search complete: 2 paths reach (2, 2) — "DDRR", "DRDR". Marking cells visited only for the duration of the current branch (and unmarking on backtrack) is what lets a cell be revisited safely on a different path.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rat in a Maze in the editorAll Backtracking problemsBack to roadmap