DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

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

Maze Size: 7×7

Speed: 600ms

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

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

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

Maze Size: 7×7

Speed: 600ms

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