Algorithm Guidecomplexity: O(4^(N·M))

Maze Solver

The problem of finding a path from start to goal in a grid maze. It's solved with backtracking: push forward in one direction, and when you hit a wall or dead end, return to the last junction and try another direction.

01Maze Solver

Explore How It Works

Maze escape. From start S to goal G, push in one direction and, when blocked, return to the last fork.

From S, step down one cell into (1,0).

Keep heading down to (2,0).

(2,0) is a dead end — walls to the right and below. Drop this branch and backtrack.

Back at S, this time go right into (0,1).

Follow the path down: (0,2) → (1,2) → (2,2).

Through (2,3), reach (3,3) G! Backtracking out of the dead end completed the path.

Live Python

1def solve(r, c):

2 if out_of_bounds(r, c) or grid[r][c] == WALL:

3 return False

4 if (r, c) in visited:

5 return False

6 visited.add((r, c)); path.append((r, c))

7 if (r, c) == goal:

8 return True

9 for dr, dc in [(1,0), (0,1), (-1,0), (0,-1)]:

10 if solve(r + dr, c + dc):

11 return True

12 path.pop() # dead end → backtrack

13 return False

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Follows one direction as far as it goes, and on hitting a dead end returns to the last junction to take a branch it has not tried.

💡In Plain Words

Go as far as you can in one direction, and at a dead end return to the last fork to try another (DFS backtracking).

It sweeps every path systematically.

📍Where It's Used

–Pathfinding
–mazes and puzzles
–game AI navigation

03 Python Implementation

A clean, readable reference implementation of the core logic of Maze Solver.

core_implementation.py

def solve_maze(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    path = []
    seen = set()

    def backtrack(r, c):
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if grid[r][c] != 0 or (r, c) in seen:
            return False
        seen.add((r, c)); path.append((r, c))
        if (r, c) == goal:
            return True
        for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if backtrack(r + dr, c + dc):
                return True
        path.pop()       # dead end → backtrack
        return False

    return path if backtrack(*start) else None

04 Frequently Asked Questions

FAQ

What is Maze Solver?+

What is the time complexity of Maze Solver?+

The time complexity of Maze Solver is O(4^(N·M)). Follow the step-by-step visualization to see exactly why.

Where is Maze Solver used?+

Pathfinding, mazes and puzzles, game AI navigation.

What's a simple analogy for Maze Solver?+

Follows one direction as far as it goes, and on hitting a dead end returns to the last junction to take a branch it has not tried.

→ Backtracking — see allRelated