BacktrackingRecursion & Backtracking
Maze Search (DFS backtracking)
Find a path from start to exit in a grid by recursively stepping into open neighbors, marking cells on the current path and unmarking on retreat.
S
.
#
.
.
.
.
#
#
.
#
.
.
.
.
.
#
.
.
#
.
#
.
.
.
#
.
.
.
T
Path stack (0)
empty
1/18DFS from S at (0,0) to T at (4,5). The recursion stack doubles as the path; dead ends are undone by popping.
StartTargetWallCurrent cellCurrent pathDead end (visited)
PseudocodeLearn Maze Search (Grid Backtracking) →
1dfs(r, c):2 if out of bounds or wall or visited: return false3 visited[r][c] = true; path.push((r,c))4 if (r,c) == T: return true5 for each direction: if dfs(next): return true6 path.pop(); return false // backtrackVariables
rows5
cols6
Complexity
worst O(R · C) for one path; exponential for all paths
space O(R · C)
Speed