DSAverse

Backtracking

Loading Backtracking...

N-Queens Board

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Backtracking

Rat in a Maze

Navigate from the top-left to the bottom-right of a binary maze. Backtracking explores all paths, marking visited cells and retreating from dead ends.

Time: O(2^(n²))

Space: O(n²)

Path Finding

Intermediate

Controls

Maze Preset

Speed: 500ms

1 / 0

Legend

Solution path

Current cell

Backtracking from

Active path

Dead end (backtracked)

Open, unvisited

Wall

Status

Position:—

Path cells:0

Dead ends:0

Click Play to begin.

Test Yourself

Q1/3

In what order does the standard Rat in a Maze algorithm try moves?

5×5 Maze — S to E

START

Rat Position—

Path Length0

Dead Ends Hit0

Algorithm Analysis

Complexity

Time: O(2^(n²)) worst case
Space: O(n²) for path tracking
Walls prune the search space heavily
BFS preferred for shortest path

Variants

Find all paths (not just first)
Shortest path via BFS instead
Weighted cells (cost-aware)
Multiple exits / start points
Diagonal movement allowed

Backtracking (Python)

Python

def solve_maze(maze):
    n = len(maze)
    path = []

    def dfs(r, c):
        # Out of bounds, wall, or already visited
        if (r < 0 or r >= n or c < 0 or c >= n
                or maze[r][c] == 0
                or (r, c) in set(path)):
            return False

        path.append((r, c))

        if r == n - 1 and c == n - 1:
            return True  # reached exit

        # Try Down, Right, Up, Left
        for dr, dc in [(1,0),(0,1),(-1,0),(0,-1)]:
            if dfs(r + dr, c + dc):
                return True

        path.pop()  # backtrack
        return False

    if dfs(0, 0):
        return path   # solution path
    return None       # no solution

DSAverse

Backtracking

Loading Backtracking...

N-Queens Board