Topics › Recursion and Backtracking › Trying out all Combos / Hard

Sudoku Solver

Hard TUF ID 873 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a 9 x 9 Sudoku board as char[][]. Filled cells hold a digit '1'-'9'; empty cells hold '.'. Fill the empty cells in place so that every row, every column and each of the nine 3 x 3 boxes contains the digits 1 to 9 exactly once. The given puzzle is guaranteed to have exactly one solution. Our methods return true when the board was completed and false when it cannot be, which makes them usable on arbitrary boards.

Example 1

puzzle                  solution
5 3 . | . 7 . | . . .   5 3 4 | 6 7 8 | 9 1 2
6 . . | 1 9 5 | . . .   6 7 2 | 1 9 5 | 3 4 8
. 9 8 | . . . | . 6 .   1 9 8 | 3 4 2 | 5 6 7
------+-------+------   ------+-------+------
8 . . | . 6 . | . . 3   8 5 9 | 7 6 1 | 4 2 3
4 . . | 8 . 3 | . . 1   4 2 6 | 8 5 3 | 7 9 1
7 . . | . 2 . | . . 6   7 1 3 | 9 2 4 | 8 5 6
------+-------+------   ------+-------+------
. 6 . | . . . | 2 8 .   9 6 1 | 5 3 7 | 2 8 4
. . . | 4 1 9 | . . 5   2 8 7 | 4 1 9 | 6 3 5
. . . | . 8 . | . 7 9   3 4 5 | 2 8 6 | 1 7 9

Example 2

row 0 = "12345678."  and  row 1 = "........9", everything else empty
answer = false      // cell (0,8) must be 9, but column 8 already contains a 9

Approach 1: Brute force, fill the first empty cell with a scanned check

Intuition. Pick an empty cell, try each digit, and for each digit ask “does it already appear in this row, this column or this box?” by scanning those 27 cells. If a digit is allowed, write it and recurse to the next empty cell. If the recursion eventually fails for every digit, this cell has no valid option under the current partial fill, so erase it and return false; the caller then moves on to its own next digit. That return is the backtracking.

The recursion stops in one of two ways: the scan finds no empty cell (board complete, true), or a cell has no legal digit (false).

Algorithm.

1. Scan rows then columns for the first '.'. If none, return true.
2. For d in '1'..'9': if canPlace(r, c, d), set the cell, recurse; on true propagate; otherwise reset to '.'.
3. Return false after all nine digits fail.

static boolean bruteForce(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 (bruteForce(board)) return true;
                    board[r][c] = '.';               // undo and try the next digit
                }
            }
            return false;                            // no digit fits this cell: backtrack
        }
    }
    return true;                                     // no empty cell is left
}

private static boolean canPlace(char[][] board, int r, int c, char d) {
    int br = r - r % 3, bc = c - c % 3;              // top-left corner of the 3x3 box
    for (int i = 0; i < 9; i++) {
        if (board[r][i] == d) return false;
        if (board[i][c] == d) return false;
        if (board[br + i / 3][bc + i % 3] == d) return false;
    }
    return true;
}

The box walk board[br + i / 3][bc + i % 3] for i = 0..8 visits the nine cells of the box row by row, so a single loop checks all three units.

Complexity. Time O(9^E) in the worst case where E is the number of empty cells, times O(81) to find the next empty cell and O(27) per check. Space O(E) recursion depth; the board is modified in place.

The return false inside the double loop is easy to get wrong: it must sit after the digit loop of the first empty cell, not after the outer loops, otherwise the method would continue scanning for a second empty cell after failing on the first.

Approach 2: Better, constant-time checks with bitmasks

Intuition. Scanning 27 cells for every digit tried is wasteful: the set of digits present in a row never changes except when we place or remove one. Keep three int arrays, rows[9], cols[9], boxes[9], where bit d of rows[r] is set when digit d is in row r. The test “is d legal at (r, c)?” becomes one OR and one AND. Placing sets the bit in all three masks; undoing clears it with XOR.

We also stop rescanning the board from (0, 0) each time: passing the linear position pos = 9r + c and advancing from it finds the next empty cell in amortised constant time.

Algorithm.

1. Build the three masks from the given digits.
2. fillInOrder(pos): advance pos past filled cells; pos == 81 means done.
3. used = rows[r] | cols[c] | boxes[b]. For each d whose bit is not in used: place, set bits, recurse on pos + 1, undo on failure.

static boolean better(char[][] board) {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') {
                int bit = 1 << (board[r][c] - '0');
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[boxOf(r, c)] |= bit;
            }
        }
    }
    return fillInOrder(board, 0, rows, cols, boxes);
}

private static boolean fillInOrder(char[][] board, int pos, int[] rows, int[] cols, int[] boxes) {
    while (pos < 81 && board[pos / 9][pos % 9] != '.') pos++;
    if (pos == 81) return true;
    int r = pos / 9, c = pos % 9, b = boxOf(r, c);
    int used = rows[r] | cols[c] | boxes[b];
    for (int d = 1; d <= 9; d++) {
        int bit = 1 << d;
        if ((used & bit) != 0) continue;
        board[r][c] = (char) ('0' + d);
        rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
        if (fillInOrder(board, pos + 1, rows, cols, boxes)) return true;
        rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
        board[r][c] = '.';
    }
    return false;
}

with boxOf(r, c) = (r / 3) * 3 + c / 3, numbering the boxes 0..8 left to right, top to bottom.

Complexity. Same O(9^E) search tree as Approach 1 (identical cell order and digit order, so identical nodes), but O(1) per node instead of O(108). Space O(E) recursion plus 27 ints.

Approach 3: Optimal, most-constrained cell first

Intuition. Row-major order is a poor way to choose which cell to fill next. If some empty cell has only one legal digit, filling it first costs nothing and may unlock other cells; if some cell has zero legal digits, the current partial fill is already dead and we should backtrack immediately instead of filling dozens of other cells first. The minimum remaining values heuristic does exactly that: at every step, compute the candidate mask of each empty cell and branch on the cell with the fewest candidates.

This heuristic is why constraint solvers finish the hardest newspaper puzzles in microseconds. On Arto Inkala’s puzzle (21 clues, in the test file) the row-major solvers try about 446 000 digit placements; the most-constrained-first solver visits about 10 000 nodes.

Algorithm.

1. Build the masks and count the empty cells.
2. fillMostConstrained(empty): if empty == 0, return true.
3. For every empty cell compute cand = ALL & ~(rows[r] | cols[c] | boxes[b]) and keep the cell with the smallest bitCount.
4. If the best count is 0, return false.
5. For each candidate bit (lowest first): place, recurse with empty - 1, undo on failure.

static boolean optimal(char[][] board) {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    int empty = 0;
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                empty++;
            } else {
                int bit = 1 << (board[r][c] - '0');
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[boxOf(r, c)] |= bit;
            }
        }
    }
    return fillMostConstrained(board, empty, rows, cols, boxes);
}

private static boolean fillMostConstrained(char[][] board, int empty, int[] rows, int[] cols, int[] boxes) {
    if (empty == 0) return true;
    int bestR = -1, bestC = -1, bestCand = 0, bestCount = 10;
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;
            int cand = ALL & ~(rows[r] | cols[c] | boxes[boxOf(r, c)]);
            int count = Integer.bitCount(cand);
            if (count < bestCount) {
                bestCount = count;
                bestCand = cand;
                bestR = r;
                bestC = c;
            }
        }
    }
    if (bestCount == 0) return false;                // an empty cell has no legal digit: dead end
    int b = boxOf(bestR, bestC);
    for (int cand = bestCand; cand != 0; cand &= cand - 1) {
        int bit = cand & -cand;                      // lowest remaining candidate
        int d = Integer.numberOfTrailingZeros(bit);
        board[bestR][bestC] = (char) ('0' + d);
        rows[bestR] |= bit; cols[bestC] |= bit; boxes[b] |= bit;
        if (fillMostConstrained(board, empty - 1, rows, cols, boxes)) return true;
        rows[bestR] ^= bit; cols[bestC] ^= bit; boxes[b] ^= bit;
        board[bestR][bestC] = '.';
    }
    return false;
}

ALL is 0b1111111110, the mask with bits 1..9 set. cand & -cand isolates the lowest set bit and cand &= cand - 1 clears it, the standard way to iterate over the bits of a mask; numberOfTrailingZeros turns the bit back into a digit.

Dry run on Example 1, first few decisions:

Easy puzzles never branch under this heuristic; hard ones branch rarely (never more than two candidates on Inkala’s puzzle) and fail fast.

Complexity. Choosing the cell costs O(81) per node, but the number of nodes collapses: roughly ten thousand for the hardest published puzzles versus hundreds of thousands of placements for row-major order, and zero backtracking on ordinary ones. Worst case remains exponential, which is unavoidable since general Sudoku is NP-complete. Space O(E) recursion.

Edge cases and pitfalls

• Already solved board. No empty cell: all three methods return true immediately without touching anything.
• Unsolvable board. Example 2 returns false, and the brute force leaves the board exactly as it was (every write was undone). LeetCode never gives such input, but a solver that can report failure is far easier to test.
• Invalid givens. The code assumes the given digits do not conflict. A row that already contains two 5s is not detected; add a validation pass if the input is untrusted.
• Character versus digit. The board stores char. board[r][c] - '0' converts to an int for the bitmask, and (char) ('0' + d) converts back. Forgetting the cast does not compile; forgetting the '0' offset silently writes control characters.
• Undo order. Clear the masks and reset the cell to '.' after a failed recursion. A stale digit left in the cell is skipped by the “find next empty” scan and makes the solver claim success on a broken board.
• Bit 0 is unused. Digits map to bits 1..9; ALL must not include bit 0, otherwise bitCount and the candidate loop would offer digit 0.

Related problems

• N Queen introduces the same row, column and diagonal occupancy arrays for O(1) checks.
• M Coloring Problem is the general graph colouring problem; Sudoku is an instance with 81 vertices and 9 colours.
• Word Search also mutates the grid in place and restores it on the way back.
• Rat in a Maze enumerates all solutions where this problem stops at the first one.