LeetCode 37困难回溯
解数独 图解题解
这道题到底在问什么
盘里 . 是空格。填数规则：同一行不能有重复数字，同一列不能有重复，同一个 3×3 宫格内也不能重复。把所有空格填满且不违规。
- 输入
- 仅剩 12 个空格的盘
- 输出
- 唯一填法
最优解：一步一步想明白
- 3核心三步：找空格 → 试 1-9 查冲突 → 合法就填并递归，不行就回溯换数。
- 4这是起始盘：绿色是题目给定的数字（固定不动），浅蓝是要填的 12 个空格。从左上角第一个空格开始。
- 5轮到空格 (0,2)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 6(0,2) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 7(0,2) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 8(0,2) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 9(0,2) 试 4：同行、同列、同宫都没有 4，合法！填进去，去找下一个空格。
- 10轮到空格 (0,6)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 11(0,6) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 12(0,6) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 13(0,6) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 14(0,6) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 15(0,6) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
- 16(0,6) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
- 17(0,6) 试 7：同行/同列/同宫里已经有 7 了，撞了，擦掉换下一个。
- 18(0,6) 试 8：同行/同列/同宫里已经有 8 了，撞了，擦掉换下一个。
- 19(0,6) 试 9：同行、同列、同宫都没有 9，合法！填进去，去找下一个空格。
- 20轮到空格 (1,3)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 21(1,3) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
- 22轮到空格 (1,7)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 23(1,7) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 24(1,7) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 25(1,7) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 26(1,7) 试 4：同行、同列、同宫都没有 4，合法！填进去，去找下一个空格。
- 27轮到空格 (2,0)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 28(2,0) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
- 29轮到空格 (2,5)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 30(2,5) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 31(2,5) 试 2：同行、同列、同宫都没有 2，合法！填进去，去找下一个空格。
- 32轮到空格 (4,4)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 33(4,4) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 34(4,4) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 35(4,4) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 36(4,4) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 37(4,4) 试 5：同行、同列、同宫都没有 5，合法！填进去，去找下一个空格。
- 38轮到空格 (5,1)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 39(5,1) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
- 40轮到空格 (5,8)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 41(5,8) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 42(5,8) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 43(5,8) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 44(5,8) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 45(5,8) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
- 46(5,8) 试 6：同行、同列、同宫都没有 6，合法！填进去，去找下一个空格。
- 47轮到空格 (7,2)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 48(7,2) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 49(7,2) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 50(7,2) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 51(7,2) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 52(7,2) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
- 53(7,2) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
- 54(7,2) 试 7：同行、同列、同宫都没有 7，合法！填进去，去找下一个空格。
- 55轮到空格 (7,6)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 56(7,6) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 57(7,6) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 58(7,6) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 59(7,6) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 60(7,6) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
- 61(7,6) 试 6：同行、同列、同宫都没有 6，合法！填进去，去找下一个空格。
- 62轮到空格 (8,4)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
- 63(8,4) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
- 64(8,4) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
- 65(8,4) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
- 66(8,4) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
- 67(8,4) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
- 68(8,4) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
- 69(8,4) 试 7：同行/同列/同宫里已经有 7 了，撞了，擦掉换下一个。
- 70(8,4) 试 8：同行、同列、同宫都没有 8，合法！填进去，去找下一个空格。
- 71所有空格都合法填满了，每行、每列、每宫的 1-9 都不重复——数独解出。
⚠️ 容易写错的地方
✗ 错：回溯时忘了把格擦回 .
✓ 对：换数前必须撤销当前填值
残留的旧值会污染后续合法性判断
✗ 错：只查行和列，漏了 3×3 宫
✓ 对：三处都要查
宫内重复同样违规，最易漏
✗ 错：宫起点写成 r/3 不乘 3
✓ 对：br=r/3*3, bc=c/3*3
要的是宫左上角坐标，不是宫编号
完整代码（Python / C++ / Java）
Python
def solveSudoku(board):
def valid(r, c, ch):
for k in range(9):
if board[r][k] == ch: return False # 同行
if board[k][c] == ch: return False # 同列
br, bc = r//3*3, c//3*3
for i in range(3):
for j in range(3):
if board[br+i][bc+j] == ch: return False # 同宫
return True
def dfs():
for r in range(9):
for c in range(9):
if board[r][c] == ".":
for ch in "123456789":
if valid(r, c, ch):
board[r][c] = ch
if dfs(): return True
board[r][c] = "." # 回溯
return False
return True
dfs()C++
class Solution {
bool valid(vector<vector<char>>& b,int r,int c,char ch){
for(int k=0;k<9;k++){
if(b[r][k]==ch) return false; // 同行
if(b[k][c]==ch) return false; // 同列
}
int br=r/3*3, bc=c/3*3;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)
if(b[br+i][bc+j]==ch) return false; // 同宫
return true;
}
bool dfs(vector<vector<char>>& b){
for(int r=0;r<9;r++)for(int c=0;c<9;c++)
if(b[r][c]=='.'){
for(char ch='1';ch<='9';ch++)
if(valid(b,r,c,ch)){
b[r][c]=ch;
if(dfs()) return true;
b[r][c]='.'; // 回溯
}
return false;
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& b){ dfs(b); }
};Java
class Solution {
boolean valid(char[][] b, int r, int c, char ch) {
for (int k = 0; k < 9; k++) {
if (b[r][k] == ch) return false; // 同行
if (b[k][c] == ch) return false; // 同列
}
int br = r / 3 * 3, bc = c / 3 * 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (b[br + i][bc + j] == ch) return false; // 同宫
return true;
}
boolean dfs(char[][] b) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] == '.') {
for (char ch = '1'; ch <= '9'; ch++)
if (valid(b, r, c, ch)) {
b[r][c] = ch;
if (dfs(b)) return true;
b[r][c] = '.'; // 回溯
}
return false;
}
return true;
}
public void solveSudoku(char[][] board) { dfs(board); }
}复杂度
时间
O(9^k)
k=空格数，每格最多试 9 个数（剪枝后远小于此）
空间
O(k)
递归栈深度 = 空格数；原地改盘不额外开盘
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 解数独 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么让数独求解更快？+
用「最少候选优先」：每次选可填数字最少的空格先填，分支更少；再配位运算记录每行/列/宫已用数字，O(1) 判合法。
怎么判断数独有没有唯一解？+
求解时不在找到第一个解就返回，继续搜，统计解的个数；个数为 1 即唯一。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 解数独 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。