解数独 图解题解

这道题到底在问什么

board

9×9 棋盘，部分已填，其余是 .

输出

原地把每个 . 填成唯一解

先想最直接的笨办法

算法从 1 试到 9，挨个查。这里演示试到 5：本行最左已有 5（题目原本就给的），重复，跳过。（动画第 6 步）

最优解：一步一步想明白

1. 3假如有 50 个空格，每格瞎填 1 到 9，就是 9 的 50 次方种填法，宇宙毁灭都算不完。所以不能盲填，得边填边检查、错了立刻回头。
2. 4回溯三件套：在一个空格里挑一个不冲突的数填进去，往下递归填后面的格；要是后面怎么都填不通，就把这个数擦掉，回来换下一个试。
3. 5看左上角 3×3 宫，焦点是右上角的空格我们把镜头对准左上角这个九宫格。算法找到的第一个空格在右上角，标成蓝色，现在要给它挑一个数。
4. 6本行已有 5，冲突，跳过算法从 1 试到 9，挨个查。这里演示试到 5：本行最左已有 5（题目原本就给的），重复，跳过。
5. 7本行已有 3，冲突，跳过再试 3。可这一行已经有个 3（也是题目给定的），又重复，继续划掉。检查靠的是「行、列、宫三个集合」，一查就知道行不行。
6. 8行列宫都没有 1 → 合法，填 1试到 1：本行没 1、本列没 1、本宫也没 1，三关都过！把 1 填进去，标绿，然后递归去填下一个空格。
7. 9以 (0,2)=1 这条路，深处某格无解顺着 (0,2) 填 1 继续往下递归。可走到深处，某个空格 1 到 9 全都冲突，怎么填都不行，这条路死了，得往回退。
8. 10board[0][2] 改回 .，三个集合也移除 1回到 (0,2)，把刚填的 1 擦掉，格子变回空，行、列、宫集合里的 1 也同步删掉。这一步是回溯的灵魂：不撤干净，后面就被污染。
9. 11(0,2)=2 往下走仍然失败在 (0,2) 换下一个候选 2，填进去往下递归。结果这条分支也走不通，再撤销 2，接着试下一个。
10. 12(0,2)=4 合法，往下递归没再撞墙再换 4：填进去往下递归，这回这个宫先凑齐了——5 3 4 / 6 7 2 / 1 9 8。台上只演了左上这一角，其余 80 格同理一路递归填下去，全部填通才 return True 层层上报。
11. 15一句话本质：数独就是带「合法性剪枝」的回溯，每个空格挨个试数，错了就撤回来换，直到全盘填满。
12. 17只擦格子、忘了从集合删 → 后面误判看 BUG 现场:刚才在 (0,2) 试过 1，撤销时只把格子擦成点,却忘了 rows[0].discard('1')。于是集合里 1 还占着,这一行后面再也填不了 1，本来有解也被你判成无解。
13. 21练熟这题，再去回溯专题迁移:N 皇后、单词搜索、组合/排列,都是「做选择→递归→撤销」的同一套骨架，换的只是「合法性怎么判」。卡住可问 AI 助教或去通关训练里实战。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def solveSudoku(self, board):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empty = []
        for r in range(9):
            for c in range(9):
                ch = board[r][c]
                if ch == '.':
                    empty.append((r, c))
                else:
                    b = (r // 3) * 3 + c // 3
                    rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch)

        def dfs(i):
            if i == len(empty):
                return True
            r, c = empty[i]
            b = (r // 3) * 3 + c // 3
            for ch in '123456789':
                if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                    continue
                board[r][c] = ch
                rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch)
                if dfs(i + 1):
                    return True
                rows[r].discard(ch); cols[c].discard(ch); boxes[b].discard(ch)
                board[r][c] = '.'
            return False
        dfs(0)

class Solution {
    int rows[9]={0}, cols[9]={0}, boxes[9]={0};
    vector<pair<int,int>> empty;
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') { empty.push_back({r, c}); continue; }
                int d = ch - '1', b = (r/3)*3 + c/3;
                rows[r] |= 1<<d; cols[c] |= 1<<d; boxes[b] |= 1<<d;
            }
        dfs(board, 0);
    }
    bool dfs(vector<vector<char>>& board, int i) {
        if (i == (int)empty.size()) return true;
        auto [r, c] = empty[i];
        int b = (r/3)*3 + c/3;
        for (int d = 0; d < 9; d++) {
            int m = 1<<d;
            if ((rows[r]|cols[c]|boxes[b]) & m) continue;
            board[r][c] = '1' + d;
            rows[r]|=m; cols[c]|=m; boxes[b]|=m;
            if (dfs(board, i + 1)) return true;
            rows[r]&=~m; cols[c]&=~m; boxes[b]&=~m;
            board[r][c] = '.';
        }
        return false;
    }
};

class Solution {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    List<int[]> empty = new ArrayList<>();
    public void solveSudoku(char[][] board) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') { empty.add(new int[]{r, c}); continue; }
                int d = ch - '1', b = (r/3)*3 + c/3;
                rows[r] |= 1<<d; cols[c] |= 1<<d; boxes[b] |= 1<<d;
            }
        dfs(board, 0);
    }
    boolean dfs(char[][] board, int i) {
        if (i == empty.size()) return true;
        int r = empty.get(i)[0], c = empty.get(i)[1];
        int b = (r/3)*3 + c/3;
        for (int d = 0; d < 9; d++) {
            int m = 1<<d;
            if (((rows[r]|cols[c]|boxes[b]) & m) != 0) continue;
            board[r][c] = (char)('1' + d);
            rows[r]|=m; cols[c]|=m; boxes[b]|=m;
            if (dfs(board, i + 1)) return true;
            rows[r]&=~m; cols[c]&=~m; boxes[b]&=~m;
            board[r][c] = '.';
        }
        return false;
    }
}

def dfs(i):
    if i == 待填位置总数:        # 全填完
        return True
    取出第 i 个待填位置
    for 候选 in 候选列表:
        if 候选不合法(查状态集合):   # 剪枝
            continue
        做选择(写入位置 + 状态集合加)
        if dfs(i + 1):
            return True
        撤销选择(清空位置 + 状态集合删)  # 关键
    return False

bool dfs(int i) {
    if (i == 待填总数) return true;     // 填满
    取出第 i 个位置 (r, c);
    for (候选 : 候选集) {
        if (不合法(状态)) continue;      // 剪枝
        做选择(写入 + 状态置位);
        if (dfs(i + 1)) return true;
        撤销(清空 + 状态复位);          // 关键
    }
    return false;
}

boolean dfs(int i) {
    if (i == 待填总数) return true;     // 填满
    取出第 i 个位置 (r, c);
    for (候选 : 候选集) {
        if (不合法(状态)) continue;      // 剪枝
        做选择(写入 + 状态置位);
        if (dfs(i + 1)) return true;
        撤销(清空 + 状态复位);          // 关键
    }
    return false;
}

复杂度

面试官可能追问