LeetCode 37. 解数独
题目描述
✅ 37. 解数独
题意分析
将 $9\times9$ 数独棋盘中的所有
'.'填成'1'到'9'，要求每行、每列和每个 $3\times3$ 宫内都不出现重复数字。原有数字固定，不能修改。题目保证存在唯一解，需要直接修改传入的
board，不返回另一张棋盘。本题要求完成整盘，而不只是判断已填部分是否合法；某个数字当前不冲突，也可能导致后续空格无解。
解法：回溯 + 三组占用标记
核心思路
[!blue]
先把所有空格的坐标收集到
spaces，按顺序决定它们填写的数字。搜索第idx个空格时，前idx个空格都已填好，且整个已填区域满足行、列、宫约束；当前任务是在此基础上完成剩余空格。为了快速判断候选，使用
rows[row][digit]、cols[col][digit]、boxes[box][digit]记录数字是否已经被使用。宫所在的大行是row / 3，大列是col / 3，按每行三个宫编号，得到box = row / 3 * 3 + col / 3。三张表先登记题面已有数字，之后始终与棋盘同步。对当前空格枚举
1到9，任何一张表显示已占用就不能填。若三处都未占用，填写棋盘并设置三处标记，再递归处理下一格。若后续无法完成，就恢复当前格为'.'并清除三处标记，尝试下一个数字。由于选择前确认过该数字在三处都未出现，撤销这些标记不会误删其他节点的占用。当
idx == spaces.size()时，所有空格均已合法填好，整盘就是答案。递归返回true并逐层立即结束，保留已经填好的棋盘；只有失败时才撤销。搜索枚举每个空格所有可能的合法候选，排除的都是必定违反规则的分支，所以不会漏掉题目保证存在的解。
解题步骤
- 初始化三张占用表和空格列表；Java 字段在每次调用时重新创建。
- 扫描棋盘，空格加入列表，已有数字登记到对应行、列、宫。
- 从第一个空格开始递归；若空格全部处理完，返回
true。- 枚举当前格的数字，跳过已被行、列或宫使用的候选。
- 写入合法候选并设置三处标记，递归处理下一格；若成功，直接向上返回
true。- 若失败，恢复当前格和三处标记。所有候选都失败时返回
false，让上一层更换选择。
代码实现
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)
}
复杂度分析
- 时间复杂度：以空格数 $e$ 为参数，粗略最坏上界为 $O(9^e)$。每个空格最多分出 9 个候选，每次合法性查询为 $O(1)$；固定棋盘扫描为常数开销，实际搜索会因约束剪掉大量分支。
- 空间复杂度：$O(e+1)$，空格列表和递归深度均至多为 $e$，三张固定大小的占用表为 $O(1)$。棋盘答案原地写入。
关键点总结
[!green]
- 已填部分合法，并不保证剩余部分可解，必须在失败时回退尝试。
- 棋盘与三张占用表共同描述一个搜索状态，选择和撤销都要同步更新。
- 递归成功表示完整答案已经留在棋盘中，立即返回才能保住结果。
- 只搜索预先收集的空格，自然保证题面已有数字不被修改。
易错点总结
[!yellow]
- 宫编号不能写成
row / 3 + col / 3，需要将宫所在行乘以三，否则不同宫会共用编号。- 代码直接用数字
1..9作下标，标记表第二维要开到 10，不能只开 9。- 没有登记初始数字，会让搜索填入与题面冲突的值。
- 失败时只恢复棋盘或只清除部分标记，会让下一条分支继承错误状态。
- 成功后仍执行撤销，会清掉已经得到的答案；成功和失败的返回路径必须分开。
- Java 的成员字段若只初始化一次，同一个对象再次调用可能带入旧状态，应在入口重新初始化。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 36. 有效的数独 | 中等 | 合法性检查提供行、列、宫的约束，本题在搜索时增量维护并回溯撤销。 |
| 51. N 皇后 | 困难 | 同样逐位置尝试并用约束剪枝，候选选择后必须恢复占用状态。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！