数独求解器如何用回溯法实现？（LeetCode 37）

简化版

数独求解就是「填空 + 回溯」：找到一个空格，依次试填 1–9，每填一个就检查它所在的行、列、3×3 宫是否合法；合法就填下、递归去填下一个空格；如果后面填不下去（走进死路），就撤销这个数、换下一个试。和「求所有解」的回溯不同，数独只要找到一个可行解就停，所以递归返回 boolean——一旦某条路径填满整个棋盘就层层返回 true，不再尝试其它。

详细版

void solveSudoku(char[][] board) { solve(board); }

boolean solve(char[][] b) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (b[r][c] != '.') continue;          // 跳过已填格
            for (char v = '1'; v <= '9'; v++) {    // 试填 1~9
                if (isValid(b, r, c, v)) {
                    b[r][c] = v;                   // 做选择
                    if (solve(b)) return true;     // 递归：成功就一路返回 true
                    b[r][c] = '.';                 // 撤销
                }
            }
            return false;                          // 1~9 都不行 → 回溯
        }
    }
    return true;                                   // 没有空格了 → 全部填满，成功
}

boolean isValid(char[][] b, int r, int c, char v) {
    for (int i = 0; i < 9; i++) {
        if (b[r][i] == v) return false;            // 同行
        if (b[i][c] == v) return false;            // 同列
        // 同一个 3×3 宫
        if (b[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == v) return false;
    }
    return true;
}

找空格 → 试 1~9 → 合法则填并递归 → 失败撤销，是标准回溯。
返回 boolean：找到一个完整解就 return true 层层短路，停止搜索（数独题保证唯一解，只需一个）。
合法性检查：行、列、所在 3×3 宫内不能有重复的 v。
宫内格子下标公式：3*(r/3)+i/3、3*(c/3)+i%3。

完整版教学

一、问题与约束

数独：9×9 棋盘，部分格子已填 1–9、空格用 . 表示。要填满所有空格，使得每一行、每一列、每一个 3×3 宫都恰好包含 1–9 且不重复。题目保证有唯一解，求出这个解。

这是「约束满足问题」的代表，回溯 + 剪枝是标准解法：枚举每个空格的可能值，用约束（行列宫不重复）剪掉非法填法。

二、回溯框架：找空格 → 试 1–9 → 递归

主流程扫描棋盘，遇到第一个空格 . 就进入尝试：

对这个空格，从 '1' 到 '9' 逐个试填；
用 isValid 检查填 v 是否违反行/列/宫约束——这一步就是剪枝，非法的值根本不填；
合法就把 v 填进去，递归去解剩下的棋盘；
若递归成功（返回 true），说明这个 v 能通向完整解，一路 return true；
若递归失败，把格子撤销回 .，换下一个值试。

如果 1–9 全试过都不行，说明前面某步填错了，return false 让上一层回溯。

三、返回 boolean：找到一个解就停止

这是数独和「全排列、子集、分割回文」等求所有解的回溯最大的不同：

求所有解的题：递归函数通常返回 void，到达一个解就 res.add(...)，然后继续尝试别的分支，把所有解都收集齐。
求一个可行解的数独：递归函数返回 boolean。一旦某条路径把棋盘填满（扫描时发现没有空格了，return true），就通过 if (solve(b)) return true; 层层短路返回，立刻停止所有后续尝试——因为只要一个解。

理解这个「用返回值短路、提前终止」是本题的关键，也是「存在性/可行性」类回溯的通用写法。

四、合法性检查：行、列、宫的下标公式

isValid(b, r, c, v) 判断在 (r,c) 填 v 是否合法，一次循环 i 从 0 到 8 同时查三处：

同行：b[r][i]——固定行 r，扫所有列；
同列：b[i][c]——固定列 c，扫所有行；
同宫：(r,c) 属于哪个 3×3 宫？宫的左上角是 (3*(r/3), 3*(c/3))（整除定位到宫）。宫内 9 个格用 i 遍历：行偏移 i/3（0~~2）、列偏移 i%3（0~~2），于是格子是 b[3*(r/3)+i/3][3*(c/3)+i%3]。

三处任一出现 v 就返回 false。

记忆点：定位所在宫的左上角用 3*(r/3)、3*(c/3)（先整除再乘 3，把坐标「对齐」到宫边界），宫内偏移用 i/3 和 i%3 拆出行列。

五、剪枝与优化

基础版已经用「行列宫合法性」剪枝，但还能更快：

最少候选优先（MRV 启发式）：不按顺序找第一个空格，而是优先填「可选数字最少」的空格——候选越少、越早试错、剪枝越猛，能显著减少搜索量。
位运算加速：用三个整数的二进制位分别记录每行、每列、每宫已用了哪些数字，isValid 和「求候选集合」都变成 O(1) 位操作，比每次扫 9 格快。

这些优化让数独在最坏情况下也能很快求解，是这题进阶考点。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：每个递归层为一个空格选择数字，行、列、3×3 宫约束始终与棋盘同步。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：位置 (r,c) 的宫编号可写 (r/3)*3+c/3；候选最少的空格优先能显著减少分支。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：题目常保证唯一解但求解器不应依赖；字符与数字转换、初始盘合法性、恢复 . 都要处理。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：固定按从左到右找空格已经最优。 MRV 选择候选最少的空格通常剪枝更强。
误区：只恢复棋盘字符即可。 行列宫标记也必须同步撤销。
误区：找到解后还要继续枚举。 只求一个解时 boolean true 应立即向上传播。
追问：宫下标怎么算？ 3×3 数独为 (r/3)*3+c/3。
追问：最坏复杂度是多少？ 粗上界可写 O(9^E)，E 为空格数，约束剪枝会大幅降低实际搜索。
追问：位掩码如何优化？ 每行列宫用 9 位表示已用数字，通过位运算得到候选。

九、加强记忆

数独求解 = 填空回溯：找空格 → 试 1–9 → isValid 查行、列、3×3 宫（合法才填，非法剪枝）→ 递归 → 失败撤销回 .。与求所有解不同，它返回 boolean，找到一个完整解就层层 return true 短路终止（存在性问题）。宫定位用 3*(r/3)、3*(c/3) 对齐宫边界、i/3 与 i%3 取宫内偏移。进阶优化：最少候选优先（MRV）+ 位运算记录行列宫占用。

简化版

详细版