DSAverse

Recursion

Loading Recursion Visualizer...

Recursion Tree

depth: 1

f(n) = f(n-1) + f(n-2)

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Recursion

Sudoku Solver

Watch constraint-based backtracking fill a 9×9 grid — place a digit, recurse, hit a dead end, erase, and try again.

Constraint satisfaction

O(9^m) time, m = empty cells

51 empty cells to fill

9×9 Grid

given trying backtrack placed

cells filled

backtracks

total placements

Starting Sudoku solver. Scanning left-to-right, top-to-bottom. For each empty cell, try digits 1–9 and recurse.

Algorithm Analysis

Constraint Checks per Cell

For each empty cell we test digits 1–9. Each test scans 9 + 9 + 9 = 27 cells (row + column + box). This is O(27) ≈ O(1) per candidate.

Worst Case vs Practice

Worst case is O(9^m) where m is the number of empty cells. In practice, constraints prune the search tree dramatically — well-formed puzzles have exactly one solution.

Real-World Applications

Puzzle generation and solving
Constraint satisfaction (CSP)
Timetable scheduling
Register allocation in compilers
Graph coloring problems

Optimizations

MRV heuristic: pick the most constrained cell first
Forward checking: detect dead-ends early
Constraint propagation (arc consistency)
Bit masks for fast validity checks

Backtracking Solver (Python)

Python

def solve_sudoku(grid):
    def is_valid(grid, row, col, num):
        if num in grid[row]: return False
        if num in [grid[r][col] for r in range(9)]: return False
        br, bc = (row // 3) * 3, (col // 3) * 3
        for r in range(br, br + 3):
            for c in range(bc, bc + 3):
                if grid[r][c] == num: return False
        return True

    def backtrack(pos=0):
        if pos == 81: return True        # solved!
        row, col = divmod(pos, 9)
        if grid[row][col] != 0:         # skip given cells
            return backtrack(pos + 1)
        for num in range(1, 10):
            if is_valid(grid, row, col, num):
                grid[row][col] = num
                if backtrack(pos + 1): return True
                grid[row][col] = 0      # backtrack

        return False  # trigger caller to backtrack

    backtrack()

Controls

Speed: 120ms / step(faster = lower)

FastSlow

Progress1 / 8367

Current State

Cell—

Trying digit—

Cells filled0 / 51

ActionSTART

Complexity

TimeO(9^m)

SpaceO(m)

Empty cells51 (m)

m = number of empty cells. Constraint pruning makes the practical complexity far lower than the worst case.

Test Yourself

Q1/3

In Sudoku backtracking, what three regions must a placed digit NOT repeat in?

DSAverse

Recursion

Loading Recursion Visualizer...

Recursion Tree

depth: 1

f(n) = f(n-1) + f(n-2)

Back to Recursion

Sudoku Solver

Watch constraint-based backtracking fill a 9×9 grid — place a digit, recurse, hit a dead end, erase, and try again.

Constraint satisfaction

O(9^m) time, m = empty cells

51 empty cells to fill

9×9 Grid

given trying backtrack placed

cells filled

backtracks

total placements

Starting Sudoku solver. Scanning left-to-right, top-to-bottom. For each empty cell, try digits 1–9 and recurse.

Algorithm Analysis

Constraint Checks per Cell

For each empty cell we test digits 1–9. Each test scans 9 + 9 + 9 = 27 cells (row + column + box). This is O(27) ≈ O(1) per candidate.

Worst Case vs Practice

Worst case is O(9^m) where m is the number of empty cells. In practice, constraints prune the search tree dramatically — well-formed puzzles have exactly one solution.

Real-World Applications

Puzzle generation and solving
Constraint satisfaction (CSP)
Timetable scheduling
Register allocation in compilers
Graph coloring problems

Optimizations

MRV heuristic: pick the most constrained cell first
Forward checking: detect dead-ends early
Constraint propagation (arc consistency)
Bit masks for fast validity checks

Backtracking Solver (Python)

Python

def solve_sudoku(grid):
    def is_valid(grid, row, col, num):
        if num in grid[row]: return False
        if num in [grid[r][col] for r in range(9)]: return False
        br, bc = (row // 3) * 3, (col // 3) * 3
        for r in range(br, br + 3):
            for c in range(bc, bc + 3):
                if grid[r][c] == num: return False
        return True

    def backtrack(pos=0):
        if pos == 81: return True        # solved!
        row, col = divmod(pos, 9)
        if grid[row][col] != 0:         # skip given cells
            return backtrack(pos + 1)
        for num in range(1, 10):
            if is_valid(grid, row, col, num):
                grid[row][col] = num
                if backtrack(pos + 1): return True
                grid[row][col] = 0      # backtrack

        return False  # trigger caller to backtrack

    backtrack()

Controls

Speed: 120ms / step(faster = lower)

FastSlow

Progress1 / 8367

Current State

Cell—

Trying digit—

Cells filled0 / 51

ActionSTART

Complexity

TimeO(9^m)

SpaceO(m)

Empty cells51 (m)

m = number of empty cells. Constraint pruning makes the practical complexity far lower than the worst case.

Test Yourself

Q1/3

In Sudoku backtracking, what three regions must a placed digit NOT repeat in?