Solving Mazes

Mazes are a classic application of backtracking. We explore paths, and when we hit a dead end, we backtrack and try a different route. This pattern applies to any grid-based path-finding problem.

Problem Setup

Given a 2D grid where:

• 0 = open path
• 1 = wall
• Start at top-left (0, 0)
• Goal is bottom-right (n-1, m-1)

Find a path (or all paths) from start to goal.

Grid:
0 0 1 0
0 0 0 0
1 0 1 0
0 0 0 0

One valid path:
→ → ↓ .
. ↓ ← ↓
. ↓ . ↓
. → → →

Basic Path Finding

def find_path(grid):
    if not grid or grid[0][0] == 1:
        return []

    rows, cols = len(grid), len(grid[0])
    path = []

    def backtrack(r, c):
        # Check bounds and obstacles
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if grid[r][c] == 1:
            return False

        # Check if visited
        if (r, c) in path:
            return False

        # Add to path
        path.append((r, c))

        # Check if we reached the goal
        if r == rows - 1 and c == cols - 1:
            return True

        # Try all four directions
        if (backtrack(r + 1, c) or  # Down
            backtrack(r, c + 1) or  # Right
            backtrack(r - 1, c) or  # Up
            backtrack(r, c - 1)):   # Left
            return True

        # Backtrack
        path.pop()
        return False

    if backtrack(0, 0):
        return path
    return []

Using a Visited Set

More efficient with a separate visited set:

def find_path_visited(grid):
    if not grid or grid[0][0] == 1:
        return []

    rows, cols = len(grid), len(grid[0])
    path = []
    visited = set()

    def backtrack(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if grid[r][c] == 1 or (r, c) in visited:
            return False

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

        if r == rows - 1 and c == cols - 1:
            return True

        # Explore neighbors
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for dr, dc in directions:
            if backtrack(r + dr, c + dc):
                return True

        # Backtrack
        path.pop()
        visited.remove((r, c))  # Allow revisiting in other paths
        return False

    if backtrack(0, 0):
        return path
    return []

Find All Paths

def find_all_paths(grid):
    if not grid or grid[0][0] == 1:
        return []

    rows, cols = len(grid), len(grid[0])
    all_paths = []
    current_path = []
    visited = set()

    def backtrack(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 1 or (r, c) in visited:
            return

        visited.add((r, c))
        current_path.append((r, c))

        if r == rows - 1 and c == cols - 1:
            all_paths.append(current_path.copy())
        else:
            directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            for dr, dc in directions:
                backtrack(r + dr, c + dc)

        # Backtrack
        current_path.pop()
        visited.remove((r, c))

    backtrack(0, 0)
    return all_paths

Visualizing the Backtracking Process

Grid:
0 0 1
0 0 0
1 0 0

Step-by-step:

1. Start (0,0), path=[(0,0)]
   Try right: (0,1)

2. At (0,1), path=[(0,0), (0,1)]
   Try right: blocked by wall
   Try down: (1,1)

3. At (1,1), path=[(0,0), (0,1), (1,1)]
   Try right: (1,2)

4. At (1,2), path=[(0,0), (0,1), (1,1), (1,2)]
   Try down: (2,2) - GOAL!

Path found: [(0,0), (0,1), (1,1), (1,2), (2,2)]

Shortest Path (BFS is Better)

Backtracking finds A path, but not necessarily the shortest. For shortest path, use BFS:

from collections import deque

def shortest_path(grid):
    if not grid or grid[0][0] == 1:
        return -1

    rows, cols = len(grid), len(grid[0])
    if rows == 1 and cols == 1:
        return 1

    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nr, nc = r + dr, c + dc

            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    if nr == rows - 1 and nc == cols - 1:
                        return dist + 1

                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))

    return -1

Rat in a Maze with Direction Strings

Output the directions (D, R, U, L) instead of coordinates:

def maze_directions(grid):
    if not grid or grid[0][0] == 1:
        return []

    rows, cols = len(grid), len(grid[0])
    all_paths = []
    visited = set()

    moves = [('D', 1, 0), ('R', 0, 1), ('U', -1, 0), ('L', 0, -1)]

    def backtrack(r, c, path):
        if r == rows - 1 and c == cols - 1:
            all_paths.append(path)
            return

        for direction, dr, dc in moves:
            nr, nc = r + dr, c + dc

            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    backtrack(nr, nc, path + direction)
                    visited.remove((nr, nc))

    visited.add((0, 0))
    backtrack(0, 0, "")
    return sorted(all_paths)  # Lexicographically sorted

Path with Obstacles

Count unique paths avoiding obstacles:

def unique_paths_with_obstacles(grid):
    if not grid or grid[0][0] == 1:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def backtrack(r, c, visited):
        nonlocal count

        if r == rows - 1 and c == cols - 1:
            count += 1
            return

        for dr, dc in [(0, 1), (1, 0)]:  # Only right and down
            nr, nc = r + dr, c + dc

            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    backtrack(nr, nc, visited)
                    visited.remove((nr, nc))

    backtrack(0, 0, {(0, 0)})
    return count

Word Search in Grid

Find if a word exists in a grid by moving to adjacent cells:

def word_search(board, word):
    if not board:
        return False

    rows, cols = len(board), len(board[0])

    def backtrack(r, c, index):
        if index == len(word):
            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False

        if board[r][c] != word[index]:
            return False

        # Mark as visited
        temp = board[r][c]
        board[r][c] = '#'

        # Explore neighbors
        found = (backtrack(r + 1, c, index + 1) or
                 backtrack(r - 1, c, index + 1) or
                 backtrack(r, c + 1, index + 1) or
                 backtrack(r, c - 1, index + 1))

        # Restore
        board[r][c] = temp

        return found

    for i in range(rows):
        for j in range(cols):
            if backtrack(i, j, 0):
                return True

    return False

board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
print(word_search(board, "ABCCED"))  # True
print(word_search(board, "SEE"))     # True
print(word_search(board, "ABCB"))    # False (can't reuse cells)

Time Complexity

For an n×m grid:

• Finding one path: O(4^(n*m)) worst case
• Pruning (visited cells): Significantly reduces actual exploration
• Each cell visited at most once per path

Key Takeaways

1. Maze solving is a classic backtracking application
2. Mark cells as visited, explore neighbors, then backtrack
3. For ALL paths: remove from visited when backtracking
4. For ONE path: can leave visited marked
5. For SHORTEST path: use BFS instead
6. Direction arrays simplify exploring neighbors
7. Same pattern applies to word search, flood fill, and similar problems

Grid-based backtracking is foundational for many interview problems. The pattern—check bounds, check visited, explore, backtrack—transfers directly to more complex constraint satisfaction problems.