Maze Solver
Depth-first backtracking through a grid: extend the path into any open cell; when every direction fails, retreat and try elsewhere. Dead ends are marked so they are never retried.
- Category
- Backtracking
- Time complexity
- O(cells)
- Space complexity
- O(path)
Pseudocode
step onto a free cell recurse in 4 directions dead end → mark, step back stop when G reached
Reference implementation
def solve(x, y):
if blocked or visited: return False
path.append((x, y))
if goal: return True
for d in dirs:
if solve(x+d.x, y+d.y): return True
path.pop() # backtrack