Sudoku Solver

Fill the empty cells (.) of a 9 × 9 Sudoku so that every row, every column, and every 3 × 3 box contains each digit 1–9 exactly once. The puzzle has exactly one solution.

LeetCode: 37. Sudoku Solver

Example

Text

Input                  Output
53..7....              534678912
6..195...              672195348
.98....6.              198342567
8...6...3              859761423
4..8.3..1              426853791
7...2...6              713924856
.6....28.              961537284
...419..5              287419635
....8..79              345286179

Backtracking with scanning

Find the first empty cell, try each digit that doesn't already appear in its row, column, or box, and recurse. If the recursion fails, clear the cell and try the next digit. If no digit works, return false so the caller tries its next option.

Java

public class Main {
    static boolean canPlace(char[][] board, int r, int c, char d) {
        int br = r / 3 * 3, bc = c / 3 * 3;
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == d || board[i][c] == d || board[br + i / 3][bc + i % 3] == d) return false;
        }
        return true;
    }

    static boolean solve(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') continue;
                for (char d = '1'; d <= '9'; d++) {
                    if (canPlace(board, r, c, d)) {
                        board[r][c] = d;
                        if (solve(board)) return true;
                        board[r][c] = '.';
                    }
                }
                return false; // no digit fits here
            }
        }
        return true; // no empty cell left
    }

    public static void main(String[] args) {
        String[] rows = {"53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79"};
        char[][] board = new char[9][];
        for (int r = 0; r < 9; r++) board[r] = rows[r].toCharArray();
        solve(board);
        for (char[] row : board) System.out.println(new String(row));
    }
}

Output

Time: O(9^m) in the worst case for m empty cells, with a 27-cell scan per candidate. Real puzzles prune heavily, but hard ones can still take millions of steps. Space: O(m) for the recursion.

Optimal: bitmasks and the most constrained cell first

Two improvements make the search much faster:

Bitmasks instead of scanning. Keep a 9-bit mask of used digits for every row, column, and box. The digits allowed in a cell are ~(rows[r] | cols[c] | boxes[b]) (masked to 9 bits), computed in O(1), and placing or removing a digit flips one bit in three masks.
Fill the cell with the fewest options first. A cell with one option is forced, and a cell with zero options means the current path is wrong. Choosing it first detects dead ends right away instead of many levels deeper.

Java

public class Main {
    static class Solver {
        final char[][] board;
        final int[] rows = new int[9];
        final int[] cols = new int[9];
        final int[] boxes = new int[9];

        Solver(char[][] board) {
            this.board = board;
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    if (board[r][c] != '.') toggle(r, c, board[r][c] - '1');
                }
            }
        }

        void toggle(int r, int c, int digit) {
            int bit = 1 << digit;
            rows[r] ^= bit;
            cols[c] ^= bit;
            boxes[r / 3 * 3 + c / 3] ^= bit;
        }

        int options(int r, int c) {
            return ~(rows[r] | cols[c] | boxes[r / 3 * 3 + c / 3]) & 0x1FF;
        }

        boolean solve() {
            // Pick the empty cell with the fewest options.
            int bestR = -1, bestC = -1, bestOpts = 0;
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    if (board[r][c] == '.') {
                        int opts = options(r, c);
                        if (bestR == -1 || Integer.bitCount(opts) < Integer.bitCount(bestOpts)) {
                            bestR = r;
                            bestC = c;
                            bestOpts = opts;
                        }
                    }
                }
            }
            if (bestR == -1) return true; // no empty cell left
            int opts = bestOpts;
            while (opts != 0) {
                int digit = Integer.numberOfTrailingZeros(opts);
                opts &= opts - 1; // clear the lowest set bit
                board[bestR][bestC] = (char) ('1' + digit);
                toggle(bestR, bestC, digit);
                if (solve()) return true;
                toggle(bestR, bestC, digit);
            }
            board[bestR][bestC] = '.';
            return false;
        }
    }

    public static void main(String[] args) {
        String[] rows = {"53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79"};
        char[][] board = new char[9][];
        for (int r = 0; r < 9; r++) board[r] = rows[r].toCharArray();
        Solver solver = new Solver(board);
        solver.solve();
        for (char[] row : solver.board) System.out.println(new String(row));

        // Row 0 holds 1-8 and column 8 holds a 9 below it, so cell (0, 8) has no option.
        char[][] stuck = new char[9][9];
        for (char[] row : stuck) java.util.Arrays.fill(row, '.');
        stuck[0] = "12345678.".toCharArray();
        stuck[1][8] = '9';
        System.out.println(new Solver(stuck).solve());
    }
}

Output

Time: still exponential in the worst case, but the check per candidate drops from 27 comparisons to one bitwise operation, and the choice of cell prunes most branches: easy puzzles are solved with no backtracking at all. Space: O(m) for the recursion.

Digit d (1–9) is stored as bit d - 1 of an int. Integer.numberOfTrailingZeros finds the lowest allowed digit, and opts & (opts - 1) removes it from the set. ~ flips all 32 bits, so & 0x1FF keeps only the nine digit bits.

Edge cases

Unsolvable puzzle: solve returns false and restores the board. The last line of the second program shows one.
Several solutions: the first one found is kept. To check uniqueness, keep searching after the first solution and stop at the second.