LeetCode. 37. Sudoku Solver

On this page

A valid Sudoku board has one solution. Fill the empty cells in place so that every row, column, and 3 × 3 box contains each digit from 1 to 9 exactly once.

Problem link

Approach

For each row, column, and box, a 9-bit mask records which digits are already present. Bit d represents digit d + 1; a set bit means that digit cannot be placed there. Thus the legal digits for an empty cell are the bits in the full mask that are absent from all three corresponding masks.

At each recursive step, scan the remaining empty cells and choose the one with the fewest legal digits (minimum remaining values, or MRV). This constraint-first choice reduces the branching factor early. If a cell has no legal digit, the current branch is impossible. Otherwise, try each candidate: write it into the board and set its three mask bits, then recurse. A failed branch clears those bits and restores '.'; a successful branch returns immediately, leaving the completed solution in the input board.

For up to 81 cells, the worst-case search is exponential (at most nine choices per empty cell), while MRV makes the search practical by exposing contradictions early and narrowing branching. The auxiliary space is O(81) for the recursion and fixed-size masks; the board is modified in place.

Java

class Solution {
    private static final int FULL = (1 << 9) - 1;

    private char[][] board;
    private final int[] rows = new int[9];
    private final int[] columns = new int[9];
    private final int[] boxes = new int[9];

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            rows[i] = 0;
            columns[i] = 0;
            boxes[i] = 0;
        }
        this.board = board;
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                char cell = board[row][column];
                if (cell != '.') {
                    int bit = 1 << (cell - '1');
                    int box = (row / 3) * 3 + column / 3;
                    rows[row] |= bit;
                    columns[column] |= bit;
                    boxes[box] |= bit;
                }
            }
        }
        solve();
    }

    private boolean solve() {
        int bestRow = -1;
        int bestColumn = -1;
        int bestCandidates = 0;
        int fewestChoices = 10;

        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                if (board[row][column] != '.') {
                    continue;
                }

                int box = (row / 3) * 3 + column / 3;
                int candidates = FULL & ~(rows[row] | columns[column] | boxes[box]);
                int choices = Integer.bitCount(candidates);
                if (choices < fewestChoices) {
                    bestRow = row;
                    bestColumn = column;
                    bestCandidates = candidates;
                    fewestChoices = choices;
                    if (choices <= 1) {
                        break;
                    }
                }
            }
            if (fewestChoices <= 1) {
                break;
            }
        }

        if (bestRow == -1) {
            return true;
        }
        if (bestCandidates == 0) {
            return false;
        }

        int box = (bestRow / 3) * 3 + bestColumn / 3;
        while (bestCandidates != 0) {
            int bit = bestCandidates & -bestCandidates;
            bestCandidates -= bit;
            int digit = Integer.numberOfTrailingZeros(bit);

            board[bestRow][bestColumn] = (char) ('1' + digit);
            rows[bestRow] |= bit;
            columns[bestColumn] |= bit;
            boxes[box] |= bit;

            if (solve()) {
                return true;
            }

            rows[bestRow] &= ~bit;
            columns[bestColumn] &= ~bit;
            boxes[box] &= ~bit;
            board[bestRow][bestColumn] = '.';
        }
        return false;
    }
}