LeetCode 37. 解数独——回溯+位运算加速候选数判断
LeetCode 37. 解数独——回溯+位运算加速候选数判断
适读人群：Java中高级工程师、算法进阶者 | 阅读时长：约25分钟 | 难度：困难
开篇故事
解数独是我第一次感受到"位运算不只是炫技，而是真正有实用价值"的题目。
朴素解法：对每个空格，遍历所有行、列、宫格，收集已用数字集合，然后试填每个候选数字。这个过程每次都是 O(27) 的操作（9行+9列+9宫格），整个回溯搜索树上每个节点都要做这个操作。
位运算优化：用三个 int[] rowUsed, colUsed, boxUsed，每个元素是一个9位的二进制数，每一位表示对应数字是否已经使用。候选数字 = ~(rowUsed[r] | colUsed[c] | boxUsed[r/3*3+c/3]) 的后9位，用 lowbit 操作提取每个候选数字，最坏情况每个格子只需 O(candidate_count) 次尝试，且每次状态更新是 O(1)。
这种用位掩码维护"已使用集合"的技巧，在很多组合搜索题中都有应用。今天我们把解数独的三种实现从朴素到最优一一展开。
一、题目解析
题目： 编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
空白格用 '.' 表示，且题目保证输入数独仅有一个解。
回溯框架：
- 找到第一个空格 (r, c)。
- 枚举该空格的所有候选数字（不与当前行、列、宫格冲突的数字）。
- 填入候选数字，递归解剩余空格。
- 若递归成功，返回 true；若所有候选都失败，清空当前格，返回 false（回溯）。
复杂度上界： 每个空格最多 9 种选择，最多 81 个空格，理论上界 O(9^81)，但实际因约束大量剪枝，远小于此。
二、解法一：朴素回溯（HashSet 维护约束）
代码
import java.util.*;
public class Solution_Basic {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
// 找到第一个空格，尝试填入1-9
for (char ch = '1'; ch <= '9'; ch++) {
if (isValid(board, r, c, ch)) {
board[r][c] = ch;
if (solve(board)) return true;
board[r][c] = '.'; // 回溯
}
}
return false; // 没有有效数字，当前路径失败
}
}
}
return true; // 所有格子已填
}
private boolean isValid(char[][] board, int r, int c, char ch) {
for (int i = 0; i < 9; i++) {
// 检查行
if (board[r][i] == ch) return false;
// 检查列
if (board[i][c] == ch) return false;
// 检查宫格
int boxRow = 3 * (r / 3) + i / 3;
int boxCol = 3 * (c / 3) + i % 3;
if (board[boxRow][boxCol] == ch) return false;
}
return true;
}
}复杂度分析
- 时间复杂度： 理论上 O(9^81)，实际因约束远小于此（通常在毫秒级完成）。每次 isValid 是 O(9)。
- 空间复杂度： O(81) = O(1) 的递归栈（最深81层）。
三、解法二：位运算优化（预维护候选数掩码）
位运算思路
用三个数组维护状态：
rowUsed[r]：第 r 行已使用的数字集合（9位二进制，第 i 位为1表示数字 i+1 已使用）colUsed[c]：第 c 列已使用的数字集合boxUsed[r/3*3+c/3]：对应宫格已使用的数字集合
计算候选数掩码：
int used = rowUsed[r] | colUsed[c] | boxUsed[r/3*3+c/3];
int candidates = (~used) & 0x1FF; // 取后9位（0x1FF = 0b111111111）枚举候选数字（lowbit 技巧）：
while (candidates != 0) {
int lowbit = candidates & (-candidates); // 取最低位的1
int digit = Integer.numberOfTrailingZeros(lowbit) + 1; // 该位对应的数字（1-9）
// 尝试填入 digit
rowUsed[r] |= lowbit; // 标记使用
colUsed[c] |= lowbit;
boxUsed[...] |= lowbit;
board[r][c] = (char)('0' + digit);
if (solve(...)) return true;
board[r][c] = '.'; // 回溯
rowUsed[r] ^= lowbit; // 取消标记（XOR清位）
colUsed[c] ^= lowbit;
boxUsed[...] ^= lowbit;
candidates &= candidates - 1; // 清除最低位的1，继续枚举下一个候选
}代码
public class Solution {
private int[] rowUsed = new int[9];
private int[] colUsed = new int[9];
private int[] boxUsed = new int[9]; // 索引：row/3*3 + col/3
public void solveSudoku(char[][] board) {
// 初始化：读取已有数字
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') {
int bit = 1 << (board[r][c] - '1'); // 数字 ch 对应第 (ch-'1') 位
rowUsed[r] |= bit;
colUsed[c] |= bit;
boxUsed[r/3*3 + c/3] |= bit;
}
}
}
solve(board);
}
private boolean solve(char[][] board) {
// 找第一个空格
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
int boxIdx = r/3*3 + c/3;
// 计算候选数字掩码
int used = rowUsed[r] | colUsed[c] | boxUsed[boxIdx];
int candidates = (~used) & 0x1FF; // 取后9位
while (candidates != 0) {
int lowbit = candidates & (-candidates);
int digit = Integer.numberOfTrailingZeros(lowbit) + 1;
// 填入 digit
board[r][c] = (char)('0' + digit);
rowUsed[r] |= lowbit;
colUsed[c] |= lowbit;
boxUsed[boxIdx] |= lowbit;
if (solve(board)) return true;
// 回溯
board[r][c] = '.';
rowUsed[r] ^= lowbit;
colUsed[c] ^= lowbit;
boxUsed[boxIdx] ^= lowbit;
candidates &= candidates - 1; // 清除最低位
}
return false; // 无候选数字，回溯
}
}
}
return true; // 全部填完
}
}Mermaid 图：位运算候选数计算
复杂度分析
- 时间复杂度： 与朴素版相同的理论上界，但实际由于 O(1) 的候选数计算和状态更新，常数因子大幅减小。
- 空间复杂度： O(1)，只用了 3 个长度为 9 的数组。
四、解法三：约束传播+回溯（Dancing Links 的简化版）
思路
更激进的优化：选择候选数最少的空格优先填（而不是从左到右第一个空格开始）。候选数最少的空格确定性最高，提前填入可以最快地减少其他空格的候选数，大幅减少搜索树的规模。
// 选择候选数最少的空格（最受约束原则）
int minCandidates = 10, bestR = -1, bestC = -1;
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
int used = rowUsed[r] | colUsed[c] | boxUsed[r/3*3+c/3];
int cnt = Integer.bitCount((~used) & 0x1FF);
if (cnt < minCandidates) {
minCandidates = cnt;
bestR = r; bestC = c;
}
}
}
}完整代码整合（略，逻辑与解法二相同，只是找空格的方式改变）。
五、举一反三
位掩码在搜索题中的应用
// 通用位掩码模板：用 int 维护一个集合（最多32个元素）
int used = 0; // 空集
// 加入元素 x（0-indexed）
used |= (1 << x);
// 移除元素 x
used ^= (1 << x); // 或 used &= ~(1 << x)
// 查询元素 x 是否存在
boolean hasX = (used >> x & 1) == 1;
// 枚举 used 中的所有元素
int tmp = used;
while (tmp != 0) {
int x = Integer.numberOfTrailingZeros(tmp); // 最低位1的位置
// 处理元素 x
tmp &= tmp - 1; // 清除最低位的1
}这个模板在 N 皇后（下一篇）、旅行商问题（状压DP）等题目中都有应用。
六、踩坑实录
坑一：位运算数字映射
数字 1-9 对应位 0-8（即 bit = 1 << (digit - 1)）。代码中 digit = numberOfTrailingZeros(lowbit) + 1，因为 lowbit 是第 (digit-1) 位的1，trailingZeros = digit-1，所以 digit = trailingZeros + 1。这个 +1 千万不能漏。
坑二：~used & 0x1FF 中的 0x1FF
Java 的 int 是 32 位，~used 会把所有 32 位取反，包括不需要的高位。& 0x1FF（后 9 位全为1）将高位清零，只保留我们关心的 9 位。
坑三：回溯时状态恢复用 XOR，不是 AND 或 OR
// 清除位：XOR（当且仅当该位确实是1时使用XOR，否则用 &= ~bit）
rowUsed[r] ^= lowbit; // 假设 lowbit 对应位一定为1，否则用 &= ~lowbit 更安全
// 更安全的写法
rowUsed[r] &= ~lowbit;如果一个位当前是0，XOR 会错误地将它置1。使用 &= ~lowbit 更安全，无论当前位是0还是1，都会清除该位。
坑四：宫格索引计算
宫格索引 = r/3 * 3 + c/3（整数除法）。注意不是 r/3 + c/3，这会导致索引计算错误。
七、总结
解数独是回溯+约束处理的综合考验，位运算优化是关键提升点。
核心技巧总结：
- 位掩码维护约束集合：O(1) 查询和更新，替代 HashSet 或数组的 O(n) 遍历。
- lowbit 技巧枚举候选数：
x & (-x)提取最低位，x &= x-1清除最低位。 - 最受约束原则（可选）：优先填候选数最少的格子，大幅减少搜索树规模。
| 解法 | 每格候选计算 | 状态更新 | 实际速度 |
|---|---|---|---|
| 朴素回溯 | O(27) | O(1) | 慢 |
| 位运算 | O(1) | O(1) | 快 |
| 位运算+MRV | O(81) 找最优格 | O(1) | 最快 |
补充深入讲解：数独求解的约束传播与高效剪枝
为什么数独是回溯的极佳示例
数独是一个约束满足问题（Constraint Satisfaction Problem，CSP）。约束满足问题的特点是：有一组变量（81 个格子），每个变量有一个取值域（1-9），以及一组约束（行、列、宫中不重复）。目标是找到一个完整的变量赋值，使所有约束都满足。
回溯是求解约束满足问题的通用方法。数独特别适合展示回溯，因为：约束数量适中（81 个格子，27 组约束，每组约束 9 个变量），每个变量的取值域固定（1-9），约束的检验简单直接（同行/列/宫不重复）。
相比之下，N 皇后问题（LeetCode 51）是约束满足问题的另一个经典例子，但约束检验需要检查对角线，略复杂一些。数独的约束完全基于行、列、宫的集合包含关系，逻辑清晰。
位掩码优化的细节解析
用三个 int[][] 数组分别存储每行、每列、每宫中已使用数字的位掩码，是数独回溯的常见优化。具体实现：
rowUsed[r] 是一个9位整数，第 k 位（0-indexed）为 1 表示第 r 行已经使用了数字 k+1。 colUsed[c] 类似，表示第 c 列的使用情况。 boxUsed[b] 中，b = (r/3)*3 + (c/3)，是格子 (r,c) 所在宫的编号（0-8）。
对于格子 (r,c)，可用数字的位掩码是 ~(rowUsed[r] | colUsed[c] | boxUsed[(r/3)*3+(c/3)]) & 0x1FF（取低9位，对应数字1-9）。这个位运算一步到位得到所有可用数字，而不需要分别检查行、列、宫，效率极高。
枚举可用数字时，用 x & (-x) 取最低位的 1（lowbit 操作），然后 x &= x-1 清除最低位，循环直到 x == 0。这样逐一枚举所有可用数字，每次操作 O(1)。
整体而言，位掩码优化将每个格子的候选数字计算从 O(9×3=27) 次比较降低到 O(1) 的位运算，在需要多次检查的回溯过程中，累积效果很可观。
约束传播：比基本回溯更进一步
基本回溯是"尝试-失败-回退"，每次失败后才回退。约束传播是更主动的策略：每次填入一个数字后，立刻推导出其他格子的限制，如果发现某个格子无法填入任何数字（候选集为空），提前判断失败并回退，不等到实际尝试才发现。
最简单的约束传播规则是"弧相容"（Arc Consistency）：对于每个空格，计算其候选数字集合（行、列、宫中未使用的数字）；如果某个空格的候选集合为空，当前状态无解，回退。
更强的约束传播是"唯一候选"：如果某行/列/宫中，某个数字只有一个格子可以填（即这个数字的候选格子集合大小为1），则必须在这个格子填入这个数字（无论该格子有多少其他候选数字）。这能在不回溯的情况下确定一些格子的值，大大减少回溯的搜索空间。
在专业数独求解器中，约束传播（包括多种高级规则）往往能不回溯地解决大多数"简单"和"中等"难度的数独，只有"困难"级别的数独才需要回溯。LeetCode 37 的测试用例包含了这些困难情况，基本回溯加位掩码剪枝足以通过。
最少候选策略（MRV 启发式）
选择下一个填入的格子时，选择候选数字最少的格子（Minimum Remaining Values，MRV）是一种有效的启发式。候选数字越少，这个格子的选择余地越小，"此路不通"的可能性越大——越早处理，就能越早发现和剪掉无效分支。
相反，如果每次按从左到右、从上到下的顺序选格子（固定顺序），可能在填了很多格子之后才发现某个格子无解，此时需要回退很多步。MRV 让我们尽早遇到"瓶颈"格子，提高剪枝效率。
对于 LeetCode 37，由于输入数独已经有部分数字填好，哪些格子空着是动态的，实现 MRV 需要在每次填入后更新候选集合，代码复杂度增加。在比赛中，通常直接用基本顺序加位掩码剪枝，代码更简洁，对于 9×9 数独足够快。
数独与编程语言的性能对比
数独是著名的编程语言性能测试基准。由于回溯过程涉及大量的整数比较和位运算，不同语言的性能差异显著：
C/C++ 实现的最优数独求解器能在微秒级内解决大多数数独；Java 实现由于 JVM 开销，通常慢 3-10 倍，但在 LeetCode 的时间限制内（通常几十毫秒）绰绰有余；Python 实现则因为解释器开销，往往需要精心优化才能通过。
这道题是展示 Java 位运算效率的好例子：通过 int 的位操作（&、|、~、>>）代替数组和循环，Java 同样能写出非常高效的代码，与 C++ 的性能差距大大缩小。
数独回溯的实现细节与调试技巧
数独回溯（LeetCode 37）的代码实现有几个容易出错的细节，掌握这些细节是写出正确代码的关键。
第一个细节是空格遍历的顺序。通常用两层 for 循环从左上到右下遍历所有格子，找到第一个空格（board[r][c] == '.'）后开始 DFS。回溯时要正确地从当前格子继续查找下一个空格，不能重新从头开始（否则会重复处理已填格子）。一种简洁的实现是在 DFS 函数中传入当前格子的线性化下标（0 到 80），每次递增查找下一个空格。
第二个细节是终止条件。当所有 81 个格子都不为空时（找不到空格），说明数独已经填满，此时结果已经写入 board，返回 true，递归栈依次返回 true，主函数结束。这是隐式的终止条件——不需要显式的 isComplete 变量，只要找不到空格就说明完成了。
第三个细节是回溯时的还原。填入一个数字，递归失败后，必须把格子恢复为空格（board[r][c] = '.'），否则下次尝试其他数字时，这个格子仍然是已填状态，会影响后续逻辑。这是回溯算法最基本的"撤销选择"步骤，在数独中尤为重要，因为 board 是直接修改的，没有路径列表可以弹出。
数独解的存在性与唯一性
LeetCode 37 的题目保证给定的数独有唯一解，这意味着我们的回溯算法一旦找到第一个合法解就可以立即停止（返回 true），不需要继续搜索其他解。这与枚举"所有"解的问题（如全排列、括号生成）不同——找到一个解就终止，大大减少了搜索量。
在代码实现中，这通过递归函数返回 boolean 来实现：如果某条分支找到了合法解，立即返回 true，调用方收到 true 也立即返回 true，这样"找到解"的信号会沿着递归栈快速传播到顶层，整个 DFS 立即终止。
如果改成求所有解（去掉"找到解就 return true"的逻辑，继续搜索），代码结构变成 void 函数，找到解时不返回而是记录，然后撤销继续。这是数独变形题的处理方式，值得了解。
数独回溯的调试方法
数独回溯是回溯类题目中代码量最大的之一，调试起来容易让人头疼。以下是一些实用的调试方法。
第一，先在小规模棋盘（如 4×4 数独）上测试。LeetCode 37 是标准的 9×9 数独，但可以先手工构造一个简单的 4×4 数独（4个 2×2 宫格，数字1-4），验证算法框架是否正确，再推广到 9×9。
第二，在关键位置打印棋盘状态。在找到每个空格并尝试填入数字时，打印当前棋盘，可以直观地看到算法的搜索过程，帮助发现回溯是否正确（撤销后棋盘是否恢复）。
第三，单独测试约束检查函数。在 isValid 函数（检查某格填入某数字是否合法）上编写单元测试，覆盖行冲突、列冲突、宫冲突三种情况以及无冲突的正常情况，确保约束检查正确后再进行整体测试。
这些调试技巧不只适用于数独，而是回溯类题目的通用调试方法：小规模验证框架，打印中间状态，独立测试子函数。
数独约束的位掩码实现要点
位掩码实现的核心是保持三个掩码数组（行、列、宫）与棋盘状态的同步。每次填入数字时，将对应位设为 1；每次撤销时，将对应位清为 0。清位操作用按位与非：mask &= ~(1 << digit)，其中 digit 是 0-indexed 的数字值（digit = num - '1'）。
如果在某个地方漏了清位（撤销时忘记更新掩码），会导致后续的候选数字计算错误，出现"某些合法数字被认为已被使用"的假阳性，导致找不到正确答案。这是位掩码实现中最常见的 bug，调试时要仔细核查每一处掩码的更新是否配对（设位和清位各一次，一一对应）。
数独回溯是约束满足问题的经典案例，位掩码优化是其工程实现的最佳实践。