Back to Recursion

Maze Solver - Backtracking

Watch recursive backtracking explore the maze, hit dead ends, and intelligently backtrack to find the solution path.

Backtracking Algorithm
O(4^(m×n)) Time
Path Finding

Controls

Legend

Start Position
Goal Position
Current Position
Current Path
Backtracking
Visited Cell
Wall

Algorithm Status

Recursion Depth:0
Path Length:0
Action: START
Solution: Searching...

Current Step

Step 1 of 0

Click Start to begin solving the maze

Maze Visualization

Algorithm: Recursive Backtracking
Strategy: Depth-First Search

Python Implementation

def solve_maze(maze, row, col, end_row, end_col, visited, path):
    # Mark current cell as visited
    visited[row][col] = True
    path.append((row, col))
    
    # Check if we reached the goal
    if row == end_row and col == end_col:
        return True  # Solution found!
    
    # Try all four directions: right, down, left, up
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    for dr, dc in directions:
        new_row, new_col = row + dr, col + dc
        
        # Check if new position is valid
        if (is_valid(new_row, new_col, maze, visited)):
            # Recursive call
            if solve_maze(maze, new_row, new_col, end_row, end_col, visited, path):
                return True
    
    # Backtrack: remove current cell from path
    path.pop()
    visited[row][col] = False
    return False

def is_valid(row, col, maze, visited):
    return (0 <= row < len(maze) and 
            0 <= col < len(maze[0]) and 
            maze[row][col] == 0 and 
            not visited[row][col])

# Solve 7×7 maze
path = []
visited = [[False] * 7 for _ in range(7)]
solution_exists = solve_maze(maze, 1, 1, 5, 5, visited, path)

JavaScript Implementation

function solveMaze(maze, row, col, endRow, endCol, visited, path) {
    visited[row][col] = true;
    path.push([row, col]);
    
    // Check if we reached the goal
    if (row === endRow && col === endCol) {
        return true;
    }
    
    // Try all directions
    const directions = [[0,1], [1,0], [0,-1], [-1,0]];
    
    for (let [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (isValid(newRow, newCol, maze, visited)) {
            if (solveMaze(maze, newRow, newCol, endRow, endCol, visited, path)) {
                return true;
            }
        }
    }
    
    // Backtrack
    path.pop();
    visited[row][col] = false;
    return false;
}

function isValid(row, col, maze, visited) {
    return row >= 0 && row < maze.length && 
           col >= 0 && col < maze[0].length && 
           maze[row][col] === 0 && !visited[row][col];
}

Algorithm Analysis

Complexity Analysis

  • • Time Complexity: O(4^(m×n)) worst case
  • • Space Complexity: O(m×n) for recursion stack
  • • Strategy: Depth-First Search with backtracking
  • • Optimization: Early termination when solution found
  • • Memory: Visited array prevents cycles

Backtracking Pattern

  • • Explore: Try a path
  • • Mark: Record current state
  • • Recurse: Go deeper
  • • Backtrack: Undo if failed
  • • Systematic: Try all possibilities

Real-World Applications

  • • Robotics: Path planning and navigation
  • • Game AI: NPC movement and pathfinding
  • • GPS Systems: Route finding algorithms
  • • Network Routing: Packet path selection
  • • Puzzle Games: Solution verification
  • • Circuit Design: Wire routing on PCBs

Algorithm Variations

  • • A* Search: Uses heuristics for efficiency
  • • Dijkstra's: Finds shortest weighted paths
  • • BFS: Finds shortest unweighted paths
  • • Wall Follower: Simple maze solving rule