Sudoku Solver Visualizer

Watch a Sudoku solver test candidates, detect conflicts, and backtrack through the puzzle with interactive controls and explanations.

Current status: Ready. Use the controls to begin exploring Sudoku Solver.

Sudoku Solver Visualizer

3
2
6
9
3
5
1
1
8
6
4
8
1
2
9
7
8
6
7
8
2
2
6
9
5
8
2
3
9
5
1
3

Try 1 at row 1, col 1.

Step 1 / 3362

Animation Legend

Trying a Digit
Digit Placed
Conflict / Backtrack
5Given Clue
5Backtracked Digit

The solver scans for the next empty cell and tries digits 1 through 9 in order. A digit is rejected if it already appears in the same row, column, or 3×3 box. If every digit fails for a cell, the algorithm backtracks: it erases the previous cell's digit and resumes trying digits there.

Java Implementation

public boolean solve(int[][] board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] != 0) continue;

            for (int num = 1; num <= 9; num++) {
                if (isValid(board, row, col, num)) {
                    board[row][col] = num;
                    if (solve(board)) return true;
                    board[row][col] = 0; // backtrack
                }
            }
            return false; // no digit works here
        }
    }
    return true; // no empty cells left
}

public boolean isValid(int[][] board, int row, int col, int num) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) return false;
    }
    int boxRow = (row / 3) * 3, boxCol = (col / 3) * 3;
    for (int r = boxRow; r < boxRow + 3; r++) {
        for (int c = boxCol; c < boxCol + 3; c++) {
            if (board[r][c] == num) return false;
        }
    }
    return true;
}
Time Complexity: O(9^m) where m = number of empty cells

How Backtracking Solves Sudoku

Sudoku is a constraint satisfaction problem: every row, column, and 3×3 box must contain the digits 1 through 9 exactly once. A backtracking solver treats it as a search - fill the next empty cell with a candidate digit, and if that choice ever makes the puzzle unsolvable, undo it and try the next candidate.

This is the same "guess, check, undo" pattern used in the N-Queens Problem, just with a much richer set of constraints per cell (row, column, and box) instead of a single conflict check.

Time & Space Complexity

  • Worst Case TimeO(9^m)
  • Space (Recursion)O(m)
  • Constraint CheckO(1)

* m = number of empty cells. Real puzzles solve far faster than the worst case thanks to early pruning.

Speeding It Up

  • ✓
    Most-Constrained Cell FirstFilling the cell with the fewest valid candidates first prunes the tree faster.
  • ✓
    Bitmask ConstraintsTracking used digits per row/column/box as bitmasks makes validity checks O(1).
  • ✓
    Constraint PropagationTechniques like naked singles fill obvious cells before any guessing begins.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Sudoku Solver Complete Info Card

BacktrackingConstraint Satisfaction

The Sudoku Solver fills one empty cell at a time, trying digits 1 through 9 and immediately undoing any choice that breaks a row, column, or box constraint.

Algorithm Characteristics

Worst Case Time

m = number of empty cells, tried digit by digit

O(9^m)

Space Complexity

Recursion depth equals the number of empty cells

O(m)

Constraint Check

Row, column, and box lookups per candidate digit

O(1)

Problem Type

Row, column, and 3×3 box constraints

Constraint Satisfaction

Search Strategy

Fill a cell, recurse, undo on dead end

Depth-First

Grid Size

81 cells, 9 rows, 9 columns, 9 boxes

9 × 9

Algorithm Steps

1

Find the next empty cell (row-major order)

2

Try digit 1 through 9 in that cell

3

Check the digit doesn't repeat in its row, column, or box

4

If valid, place it and recurse to the next empty cell

5

If no digit works, backtrack: erase and return to the previous cell

6

Stop once every cell is filled validly

When to Use

  • •Puzzles with a well-defined, valid solution
  • •Teaching constraint propagation and pruning
  • •As a baseline before adding heuristics like naked singles

When to Avoid

  • •Puzzles with very few clues (search space explodes)
  • •Production solvers needing sub-millisecond performance
  • •Generating unique puzzles (needs a separate uniqueness check)
Did You Know? A valid Sudoku puzzle needs at least 17 given clues to have a unique solution - no puzzle with fewer clues has ever been found to be uniquely solvable.
Constraint propagationRecursionPuzzle solving