Sudoku Solver in Java

advanced· Recursion · Recursion

Problem

Solving a Sudoku puzzle means filling every empty cell with a digit from 1 to 9 so that no digit repeats in any row, column, or 3 by 3 box — a digit that later turns out to block every remaining cell has to be undone and a different one tried.

Given a partially-filled 9 by 9 grid, fill in every empty cell so the completed grid satisfies Sudoku's row, column, and box rules.

Input

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

Output

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

Java Program

Java

public class SudokuSolver {
    static 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;
    }

    static boolean solve(int[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == 0) {
                    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: this digit didn't lead to a solution
                        }
                    }
                    return false; // no digit worked for this cell
                }
            }
        }
        return true; // no empty cells left
    }

    public static void main(String[] args) {
        int[][] board = {
            {0, 2, 0, 4, 0, 6, 0, 8, 0},
            {4, 0, 6, 0, 8, 0, 1, 0, 3},
            {0, 8, 0, 1, 0, 3, 0, 5, 0},
            {2, 0, 4, 0, 6, 0, 8, 0, 1},
            {0, 6, 0, 8, 0, 1, 0, 3, 0},
            {8, 0, 1, 0, 3, 0, 5, 0, 7},
            {0, 4, 0, 6, 0, 8, 0, 1, 0},
            {6, 0, 8, 0, 1, 0, 3, 0, 5},
            {0, 1, 0, 3, 0, 5, 0, 7, 0}
        };
        solve(board);
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for (int i = 0; i < row.length; i++) {
                if (i > 0) sb.append(" ");
                sb.append(row[i]);
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

▶ Run Code

Output

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

Core Logic

Scanning for the next empty cell, trying every digit that doesn't immediately break a rule, and recursing on the rest of the grid fills the whole puzzle one cell at a time, undoing a digit only when it leads nowhere.

How It Works

1isValid(board, row, col, num) checks whether num already appears in that row, that column, or that cell's 3×3 box — placing it is only safe if none of those three checks find a match.
2solve(board) scans row by row for the first empty cell (marked 0) and tries every digit 1 through 9 in it.
3Placing a valid digit and recursing lets the rest of the grid attempt to complete around that choice; if the recursive call succeeds, the whole grid is solved and true propagates back up immediately.
4If every digit fails to lead to a full solution, the cell is reset to 0 — the backtrack step — and false is returned so the caller tries its own next digit instead.

This puzzle's cells only ever have one valid digit each, given the surrounding clues, so the solver fills every empty cell on the first attempt without ever needing to backtrack — a puzzle with more ambiguity would trigger the reset step far more often.

💡

Key Point: Returning false only when every digit 1 through 9 has been tried and failed is what guarantees the search is exhaustive — no valid completion is ever skipped, even though most invalid digits are ruled out almost immediately by isValid().

Complexity

Time Complexity: O(9^m)Space Complexity: O(1)

Why: In the absolute worst case, each of the m empty cells could require trying up to 9 digits before the constraint checks and backtracking narrow things down — an enormous, deliberately loose upper bound, since in practice the row/column/box checks prune the vast majority of digit choices almost immediately for a well-posed puzzle; the grid is modified in place, so no extra memory grows with the puzzle's difficulty.

Key Concepts

recursionbacktrackingconstraint checking

← Previous

Reverse Number Using Recursion

Sum of Numbers Using Recursion

Related Programs

Recursionbeginner

Array Sum Using Recursion

Recursionbeginner

Check Palindrome Using Recursion

Recursionbeginner

Factorial Using Recursion

Recursionbeginner

Factorial

Recursionintermediate

Fibonacci Sequence