Problem statement

A Sudoku puzzle is given as 9 strings of 9 characters each, where '1'–'9' are filled cells and '.' is an empty cell. Fill every empty cell so that:

• each row contains every digit 1–9 exactly once;
• each column contains every digit 1–9 exactly once;
• each of the nine 3 x 3 boxes contains every digit 1–9 exactly once.

The puzzle is guaranteed to have exactly one solution. Return the solved board in the same format (9 strings of 9 digits).

Example 1

Input: board = ["7..43.56.","9...65712","....1.93.","1.9..3.8.","3..7.....","...921..5",".9.65.87.",".5...8.93","8....24.."]
Output: ["712439568","934865712","568217934","129543687","345786129","687921345","293654871","456178293","871392456"]

Example 2

Input: board = ["46...3...","..9...4..","..1.762.9","9..13275.",".2..8..4.","7589....3","8..6.73..","..4....75","6.5....1."]
Output: ["467293581","239518467","581476239","946132758","123785946","758964123","812657394","394821675","675349812"]

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit '1'-'9' or '.'
• the puzzle has exactly one solution

Hints for Sudoku Solver

1. Hint 1

   Keep, for every row, column and box, the set of digits already used — a 9-bit mask each makes checking a digit O(1).

2. Hint 2

   Backtracking: pick an empty cell, try each digit that fits, recurse, and undo on failure.

3. Hint 3

   Always branch on the empty cell with the fewest candidates. Cells with one candidate are forced, and a cell with zero candidates means the current branch is dead — this keeps the search tiny.

How to solve Sudoku Solver

Depth-first search over digit placements, with bitmasks for the used digits of every row, column and box, and the "most constrained cell first" rule to keep the search tree small.

Approach

1. Read the board into a grid and set bit d - 1 of rows[r], cols[c] and boxes[3 * (r / 3) + c / 3] for every given digit d.
2. Find the empty cell whose candidate mask ~(rows | cols | boxes) & 0x1FF has the fewest bits. If no cell is empty, the board is solved; if some cell has no candidates, backtrack.
3. For each candidate bit of that cell: place the digit (set the three masks), recurse, and if the recursion fails, clear the digit and the masks.
4. Return the filled board as 9 strings.

Why it works

The masks always describe exactly the digits used in each unit, so a candidate never breaks a rule, and the search tries every candidate for the chosen cell, so it cannot miss the solution. Choosing the cell with the fewest options makes forced moves happen immediately and detects contradictions early; for puzzles with a unique solution that usually means very little backtracking.

Complexity

• Time — Exponential in the worst case; a few hundred nodes for typical puzzles
• Space — O(81) for the board and the recursion

Pitfalls

• The box index is 3 * (r / 3) + c / 3 with integer division.
• Undo all three masks and the cell when backtracking, or later branches see phantom digits.
• Scanning cells in fixed order without the fewest-candidates rule can explode on hard puzzles.

Reference solution

Python

from typing import List

def solveSudoku(board: List[str]) -> List[str]:
    cells = [0] * 81
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    box_of = [(i // 27) * 3 + (i % 9) // 3 for i in range(81)]
    for i in range(81):
        ch = board[i // 9][i % 9]
        if ch != '.':
            v = ord(ch) - 48
            cells[i] = v
            bit = 1 << (v - 1)
            rows[i // 9] |= bit
            cols[i % 9] |= bit
            boxes[box_of[i]] |= bit

    def solve():
        best, best_mask, best_cnt = -1, 0, 10
        for i in range(81):
            if cells[i]:
                continue
            mask = ~(rows[i // 9] | cols[i % 9] | boxes[box_of[i]]) & 511
            cnt = bin(mask).count('1')
            if cnt < best_cnt:
                best, best_mask, best_cnt = i, mask, cnt
                if cnt <= 1:
                    break
        if best < 0:
            return True
        r, c, b = best // 9, best % 9, box_of[best]
        m = best_mask
        while m:
            bit = m & -m
            m ^= bit
            cells[best] = bit.bit_length()
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
            if solve():
                return True
            cells[best] = 0
            rows[r] ^= bit
            cols[c] ^= bit
            boxes[b] ^= bit
        return False

    solve()
    return [''.join(str(cells[r * 9 + c]) for c in range(9)) for r in range(9)]

Java

public static String[] solveSudoku(String[] board) {
    int[] cells = new int[81], rows = new int[9], cols = new int[9], boxes = new int[9];
    for (int i = 0; i < 81; i++) {
        char ch = board[i / 9].charAt(i % 9);
        if (ch == '.') continue;
        int v = ch - '0', bit = 1 << (v - 1);
        cells[i] = v;
        rows[i / 9] |= bit;
        cols[i % 9] |= bit;
        boxes[(i / 27) * 3 + (i % 9) / 3] |= bit;
    }
    sudokuSearch(cells, rows, cols, boxes);
    String[] out = new String[9];
    for (int r = 0; r < 9; r++) {
        StringBuilder sb = new StringBuilder();
        for (int c = 0; c < 9; c++) sb.append(cells[r * 9 + c]);
        out[r] = sb.toString();
    }
    return out;
}

private static boolean sudokuSearch(int[] cells, int[] rows, int[] cols, int[] boxes) {
    int best = -1, bestMask = 0, bestCnt = 10;
    for (int i = 0; i < 81; i++) {
        if (cells[i] != 0) continue;
        int mask = ~(rows[i / 9] | cols[i % 9] | boxes[(i / 27) * 3 + (i % 9) / 3]) & 511;
        int cnt = Integer.bitCount(mask);
        if (cnt < bestCnt) { best = i; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; }
    }
    if (best < 0) return true;
    int r = best / 9, c = best % 9, b = (best / 27) * 3 + c / 3;
    for (int m = bestMask; m != 0; m &= m - 1) {
        int bit = m & -m;
        cells[best] = Integer.numberOfTrailingZeros(bit) + 1;
        rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
        if (sudokuSearch(cells, rows, cols, boxes)) return true;
        cells[best] = 0;
        rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
    }
    return false;
}

C++

static bool sudokuSearch(int* cells, int* rows, int* cols, int* boxes) {
    int best = -1, bestMask = 0, bestCnt = 10;
    for (int i = 0; i < 81; i++) {
        if (cells[i]) continue;
        int mask = ~(rows[i / 9] | cols[i % 9] | boxes[(i / 27) * 3 + (i % 9) / 3]) & 511;
        int cnt = __builtin_popcount(mask);
        if (cnt < bestCnt) { best = i; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; }
    }
    if (best < 0) return true;
    int r = best / 9, c = best % 9, b = (best / 27) * 3 + c / 3;
    for (int m = bestMask; m; m &= m - 1) {
        int bit = m & -m;
        cells[best] = __builtin_ctz(bit) + 1;
        rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
        if (sudokuSearch(cells, rows, cols, boxes)) return true;
        cells[best] = 0;
        rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
    }
    return false;
}

vector<string> solveSudoku(vector<string>& board) {
    int cells[81] = {0}, rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};
    for (int i = 0; i < 81; i++) {
        char ch = board[i / 9][i % 9];
        if (ch == '.') continue;
        int v = ch - '0', bit = 1 << (v - 1);
        cells[i] = v;
        rows[i / 9] |= bit;
        cols[i % 9] |= bit;
        boxes[(i / 27) * 3 + (i % 9) / 3] |= bit;
    }
    sudokuSearch(cells, rows, cols, boxes);
    vector<string> out(9, string(9, '0'));
    for (int i = 0; i < 81; i++) out[i / 9][i % 9] = (char)('0' + cells[i]);
    return out;
}

JavaScript

var solveSudoku = function(board) {
    var cells = [], rows = [], cols = [], boxes = [], i;
    for (i = 0; i < 9; i++) { rows.push(0); cols.push(0); boxes.push(0); }
    var boxOf = function(k) { return Math.floor(k / 27) * 3 + Math.floor((k % 9) / 3); };
    var bitCount = function(x) { var k = 0; while (x) { x &= x - 1; k++; } return k; };
    for (i = 0; i < 81; i++) {
        var ch = board[Math.floor(i / 9)][i % 9];
        var v = ch === '.' ? 0 : ch.charCodeAt(0) - 48;
        cells.push(v);
        if (v) {
            var bit = 1 << (v - 1);
            rows[Math.floor(i / 9)] |= bit; cols[i % 9] |= bit; boxes[boxOf(i)] |= bit;
        }
    }
    var solve = function() {
        var best = -1, bestMask = 0, bestCnt = 10;
        for (var k = 0; k < 81; k++) {
            if (cells[k]) continue;
            var mask = ~(rows[Math.floor(k / 9)] | cols[k % 9] | boxes[boxOf(k)]) & 511;
            var cnt = bitCount(mask);
            if (cnt < bestCnt) { best = k; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; }
        }
        if (best < 0) return true;
        var r = Math.floor(best / 9), c = best % 9, b = boxOf(best);
        for (var m = bestMask; m; m &= m - 1) {
            var low = m & -m;
            cells[best] = bitCount(low - 1) + 1;
            rows[r] |= low; cols[c] |= low; boxes[b] |= low;
            if (solve()) return true;
            cells[best] = 0;
            rows[r] ^= low; cols[c] ^= low; boxes[b] ^= low;
        }
        return false;
    };
    solve();
    var out = [];
    for (var r2 = 0; r2 < 9; r2++) out.push(cells.slice(r2 * 9, r2 * 9 + 9).join(''));
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard