：二维递归的完全体——暴力破解「解数独」)
哈喽各位，我是前端小L。
欢迎来到我们的回溯算法专题第十篇！数独游戏大家应该都玩过，规则极其“简单粗暴”：
数字 1-9在每一行只能出现一次。
数字 1-9在每一列只能出现一次。
数字 1-9在每一个以粗实线分隔的3x3 宫内只能出现一次。
我们现在的任务是：写一个程序，把一个残缺的数独填完。 这道题和之前最大的不同在于：我们要找的不是“所有解”，而是“一个解”。一旦找到，立刻停止！这意味着我们的递归函数要有返回值 (bool)，用来告诉上一层：“搞定了，别试了，快撤！”
力扣 37. 解数独
https://leetcode.cn/problems/sudoku-solver/
题目分析：
输入：
9x9的二维字符数组board。空位用'.'表示。目标：原地修改
board，填入唯一的一个可行解。
核心思维：如何遍历二维空格？
在 N 皇后中，我们通过backtrack(row + 1)来控制递归深度。 但在数独中，空格是散落在棋盘各处的。 我们通常采用双重循环 + 递归的策略：
递归逻辑（伪代码）：
Plaintext
function backtrack(board): for i from 0 to 8: for j from 0 to 8: if board[i][j] is Empty: // 发现一个坑！尝试填 1-9 for k from '1' to '9': if isValid(i, j, k): 填入 k if backtrack(board) is True: return True // 找到了！一路绿灯返回 撤销 k (回溯) return False // 1-9 都试过了都不行，说明前面的步骤填错了，无解 return True // 遍历完所有格子没返回 False，说明填满了！注意到了吗？这个递归结构和之前的很不一样。它在函数内部就开启了对整个棋盘的扫描。一旦发现空格，就通过递归去填下一个空格。
isValid的九宫格判定
判断行和列很简单。难点在于判断3x3 九宫格。 对于任意坐标(r, c)，它所属的 3x3 宫的左上角坐标是：
startRow = (r / 3) * 3startCol = (c / 3) * 3通过这两个基准点，我们可以遍历该宫内的 9 个格子。
代码实现 (C++)
C++
#include <vector> using namespace std; class Solution { private: // 判断在 board[row][col] 填入 val 是否合法 bool isValid(int row, int col, char val, vector<vector<char>>& board) { // 1. 检查行 for (int j = 0; j < 9; j++) { if (board[row][j] == val) return false; } // 2. 检查列 for (int i = 0; i < 9; i++) { if (board[i][col] == val) return false; } // 3. 检查 3x3 九宫格 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++) { for (int j = startCol; j < startCol + 3; j++) { if (board[i][j] == val) return false; } } return true; } // 返回值 bool：表示是否找到了一组解 // 如果找到，立即停止后续搜索 bool backtrack(vector<vector<char>>& board) { // 遍历整个棋盘寻找空格 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { // 如果发现空格 if (board[i][j] == '.') { // 尝试填入 '1' 到 '9' for (char k = '1'; k <= '9'; k++) { if (isValid(i, j, k, board)) { // 做选择 board[i][j] = k; // 递归：如果后续的填充成功了，那我也直接返回 true if (backtrack(board)) return true; // 撤销选择 (回溯) board[i][j] = '.'; } } // 9个数字都试完了还不行，说明这个空格在这个局面下无解 // 或者是前面的步骤填错了，需要回溯 return false; } } } // 如果两个循环跑完都没有返回 false，说明没有空格了（填满了） return true; } public: void solveSudoku(vector<vector<char>>& board) { backtrack(board); } };深度复杂度分析
时间复杂度：非常恐怖。
数独的空白格可能有 M 个。
每个格子有 9 种选择。
理论上限是 O(9M)。
但由于数独的约束非常强（每填一个数，其他格子的选择就少很多），实际运行并不慢。
空间复杂度：O(M)。
递归栈的深度等于空白格的数量。
总结：回溯算法的“毕业设计”
恭喜你！这道题通过，标志着你已经攻克了回溯算法最险峻的山峰。
让我们回顾一下回溯算法的“进化史”：
组合/子集：
startIndex控制不回头，path收集结果。排列：
used数组控制不重复选，关注顺序。切割：
startIndex作为切割线，判断子串合法性。去重：
sort+nums[i] == nums[i-1]剪掉树层重复。棋盘：
N 皇后：一维决策（行），二维约束。
解数独：二维决策（每个格子），找唯一解（bool 返回值）。
这一套组合拳打下来，所有的暴力搜索问题在你面前都将无所遁形。
接下来学什么？我们已经完成了：DP（内功）、图论（招式）、回溯（暴力美学）。 接下来，我建议我们稍微“换个口味”，去探索一下算法面试中代码量最少，但思维最巧妙的领域——贪心算法 (Greedy)。
下一篇，我们将从经典的**“分发饼干”**开始，看看如何用“局部最优”推导出“全局最优”。准备好你的直觉了吗？
下期见！
)
