LeetCode 37. 解数独

2025-04-23 HGNULB 约 8 分钟

文章信息 13 个分类 6 个标签

分类

LeetCode CodeTop 困难未解决 20-50 字节跳动微软美团阿里巴巴腾讯小米亚马逊虾皮

题目描述

✅ 37. 解数独

题意分析

给定一个 $9 \times 9$ 的字符棋盘，已填格子是 '1' 到 '9' 的字符，待填格子是 '.'。要把所有 '.' 补齐，使得每一行、每一列、以及九个 $3 \times 3$ 的小宫格内部，1 到 9 各出现且仅出现一次。

交付形式很关键：函数签名没有返回值，题目要求原地修改传入的 board。判题读的是被改动后的那个二维数组，任何「另建一份新棋盘再返回」的写法都等于什么也没做。

约束里有三个强信号。第一，棋盘尺寸固定为 $9 \times 9$，规模极小但组合空间极大，$9^{81}$ 量级的朴素枚举不可能跑完，因此必须能在填错的第一时间就止损。第二，题目保证输入有且只有一个解，这意味着不需要收集所有解，一旦搜到就可以立刻沿调用链一路返回，不再继续搜索。第三，约束只有三条，而且形式完全一致：都是「某个集合内 $1$ 到 $9$ 不重复」，这种高度对称的结构提示我们可以用三张同构的表来统一维护。

边界情形：棋盘可能一开始就没有空格（全部填满），此时不需要做任何事；也可能空格很多、给定数字很少，此时搜索深度接近 81。输入保证合法且有解，所以不必处理「无解」和「初始就冲突」的情况，但代码结构上仍然要有失败返回值，否则回溯无从进行。

解法：回溯 + 三组占用标记

核心思路

数独需要在多个候选中试探，选错后撤销，因此使用回溯。关键剪枝是：放入数字前立即检查它是否已出现在当前行、当前列或当前九宫格，非法选择不再递归。

用三组布尔表维护占用状态：

rows[row][digit]：第 row 行是否已有 digit；

cols[col][digit]：第 col 列是否已有 digit；

boxes[box][digit]：第 box 宫是否已有 digit。

宫编号为 row / 3 * 3 + col / 3。这样一次合法性检查只需查三张表。预处理时还把所有空格坐标收集到 spaces，递归状态只需记录当前处理到第几个空格。

循环不变量是：进入 backtrack(idx) 时，前 idx 个空格已经合法填好，三张表与棋盘当前状态完全一致。尝试一个数字时同步写入棋盘和三张表；该分支失败时再同步撤销。

算法会枚举当前格的每个合法数字，因此不会漏掉任何可能解；被剪掉的分支已经违反数独约束，不可能成为答案。处理完所有空格时得到合法解。题目保证唯一解，所以找到后返回 true，让成功路径跳过撤销并保留在原棋盘中。

解题步骤

每次调用先重置三张占用表和空格列表，避免复用同一个 Solution 时残留状态。

扫描棋盘：数字写入对应的行、列、宫标记；'.' 的坐标加入 spaces。

从 backtrack(board, 0) 开始处理空格。

对当前空格枚举 1 到 9。若任一占用表已标记该数字，直接跳过。

合法时写入数字并设置三处标记，然后递归处理下一个空格。

子问题成功就立即返回；失败则把棋盘恢复为 '.'，并清除三处标记。

例如官方样例的第一个空格 (0, 2)：所在行已有 3、5、7，所在列已有 8，所在宫已有 3、5、6、8、9，所以候选只有 1、2、4。算法只会进入这三个分支，而不会盲目尝试九种数字。

代码实现

class Solution {
    private boolean[][] rows;
    private boolean[][] cols;
    private boolean[][] boxes;
    private java.util.List<int[]> spaces;

    public void solveSudoku(char[][] board) {
        rows = new boolean[9][10];
        cols = new boolean[9][10];
        boxes = new boolean[9][10];
        spaces = new java.util.ArrayList<>();

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    spaces.add(new int[]{row, col});
                    continue;
                }

                int digit = board[row][col] - '0';
                rows[row][digit] = true;
                cols[col][digit] = true;
                boxes[boxIndex(row, col)][digit] = true;
            }
        }
        backtrack(board, 0);
    }

    private boolean backtrack(char[][] board, int idx) {
        if (idx == spaces.size()) {
            return true;
        }

        int row = spaces.get(idx)[0];
        int col = spaces.get(idx)[1];
        int box = boxIndex(row, col);

        for (int digit = 1; digit <= 9; digit++) {
            if (rows[row][digit]
                    || cols[col][digit]
                    || boxes[box][digit]) {
                continue;
            }

            board[row][col] = (char) ('0' + digit);
            rows[row][digit] = true;
            cols[col][digit] = true;
            boxes[box][digit] = true;

            if (backtrack(board, idx + 1)) {
                return true;
            }

            board[row][col] = '.';
            rows[row][digit] = false;
            cols[col][digit] = false;
            boxes[box][digit] = false;
        }
        return false;
    }

    private int boxIndex(int row, int col) {
        return row / 3 * 3 + col / 3;
    }
}

func solveSudoku(board [][]byte) {
    rows := [9][10]bool{}
    cols := [9][10]bool{}
    boxes := [9][10]bool{}
    spaces := make([][2]int, 0)

    for row := 0; row < 9; row++ {
        for col := 0; col < 9; col++ {
            if board[row][col] == '.' {
                spaces = append(spaces, [2]int{row, col})
                continue
            }

            digit := int(board[row][col] - '0')
            box := row/3*3 + col/3
            rows[row][digit] = true
            cols[col][digit] = true
            boxes[box][digit] = true
        }
    }

    var backtrack func(int) bool
    backtrack = func(idx int) bool {
        if idx == len(spaces) {
            return true
        }

        row, col := spaces[idx][0], spaces[idx][1]
        box := row/3*3 + col/3
        for digit := 1; digit <= 9; digit++ {
            if rows[row][digit] || cols[col][digit] || boxes[box][digit] {
                continue
            }

            board[row][col] = byte('0' + digit)
            rows[row][digit] = true
            cols[col][digit] = true
            boxes[box][digit] = true

            if backtrack(idx + 1) {
                return true
            }

            board[row][col] = '.'
            rows[row][digit] = false
            cols[col][digit] = false
            boxes[box][digit] = false
        }
        return false
    }

    backtrack(0)
}

复杂度分析

时间复杂度：最坏为 $O(9^e)$，e 是空格数。每个空格最多尝试 9 个数字；行、列、宫检查均为 $O(1)$。实际分支会被约束大量剪掉。

空间复杂度：$O(e)$，包括空格列表和最深 e 层递归栈；三张固定大小的占用表是 $O(1)$。

关键点总结

回溯模板是“选择、递归、撤销”，合法性检查放在递归之前。

行、列、宫状态必须和棋盘同步更新、同步恢复。

宫编号公式是 row / 3 * 3 + col / 3。

只求一个解时让递归返回布尔值，成功后立即停止并保留答案。

进阶追问可说明：困难盘面可优先处理候选数最少的空格，进一步降低分支数。

易错点总结

宫编号写成 row / 3 + col / 3：不同九宫格会映射到同一编号。

标记数组第二维只开 9 却直接用数字作下标：访问数字 9 时越界；本实现开 10 位。

没有登记初始数字：搜索会重复使用题面已有数字。

撤销不完整：只恢复棋盘、未清除三张表，会污染后续兄弟分支。

找到答案后仍执行撤销：最终棋盘会被恢复成未完成状态，成功时必须直接返回。

实例字段不在每次调用时重置：同一个对象连续求解两盘会残留上一盘状态。

把答案写到新棋盘：题目要求原地修改传入的 board。

相似题目

题目	难度	考察点
36. 有效的数独	中等	只校验当前盘面是否合法，一次遍历建三张表即可，不涉及搜索
51. N 皇后	困难	冲突维度换成列与两条对角线，且要求输出全部解而非提前返回
52. N 皇后 II	困难	只统计解的数量，可用位掩码代替数组把常数压到极致
79. 单词搜索	中等	回溯在网格上按四邻域扩展，撤销的是访问标记而不是数值占用
46. 全排列	中等	只有「元素是否用过」一个维度的约束，是回溯框架的最小骨架
212. 单词搜索 II	困难	回溯叠加字典树剪枝，用前缀是否存在来提前砍掉整棵子树