编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用'.'表示。
难点
N皇后问题和解数独问题对比
一、 求解策略：要“全集”还是要“特例”？
N皇后 (
void)：我们需要知道一共有多少种摆法。这意味着即使找到了一组解，也不能停，必须回溯回去，继续探索其他分支。所以不需要返回值，用全局变量result收集。解数独 (
bool)：数独只需要填满棋盘即可。一旦找到一条通往叶子节点的路径（即棋盘填满），就立刻层层返回true，通过if (backtracking(...)) return true;阻断后续无意义的尝试。
二、 维度差异：一维推进 vs 二维扫描这是两道题代码结构差异的根源。
N皇后（一维问题）：
规则特性：每一行只能且必须放一个皇后。
推论：一旦第
row行确定了位置，该行的任务就结束了，直接递归进入row + 1。代码体现：递归参数只需要
row。我们在思维上把二维棋盘压扁成了 N 个的一维决策步骤。
解数独（二维问题）：
规则特性：每一行有多个空缺，且空缺位置不固定。
推论：我们不能简单地“处理完这一行去下一行”。我们需要精确定位到棋盘上的每一个坐标
(i, j)。代码体现：通用写法：每次递归都双重循环
for i, for j扫描整个棋盘去找下一个 。
三、 树的宽度与操作粒度
N皇后：是在决定“这一行的皇后放在哪一列”。（树的宽度是 N，即列数）。
解数独：是在决定“这一个格子填入哪一个数字”。（树的宽度是 9，即数字 1-9）。
代码
参数
bool backtracking(vector<vector<char>>& board) {终止条件
本题目其实不要终止条件，如果双重循环跑完了，都没有遇到 return false，说明棋盘里没有 '.' 了（填满了）
单层递归逻辑
for (int i = 0; i < board.size(); i++) { // 遍历行 for (int j = 0; j < board[0].size(); j++) { // 遍历列 // 步骤 1: 寻找空白格（'.' 表示还没填数字） if (board[i][j] == '.') { // 步骤 2: 尝试填入数字 '1' 到 '9' for (char k = '1'; k <= '9'; k++) { // 步骤 3: 检查在 (i, j) 放数字 k 是否符合数独规则 if (isValid(i, j, k, board)) { board[i][j] = k; // 【做选择】：放置数字 k // 步骤 4: 递归调用 // 如果填入 k 之后，后续的递归也能成功填满棋盘，说明找到解了 if (backtracking(board)) return true; board[i][j] = '.'; // 【撤销选择】：回溯 // 如果上面的 backtracking 返回 false，说明刚才填 k 导致后面无解 // 所以要把 k 拿走，恢复成 '.'，以便下一次循环尝试 k+1 } } // 步骤 5: 关键点 // 如果 1-9 都试过了，都不合法（或者导致后续无解），说明当前这一步就死路一条 // 返回 false 给上一层递归，告诉它“你之前填的数有问题，换一个吧” return false; } } }isValid函数
其中定位当前格子所属的 3x3 九宫格的左上角起点记一下
bool isValid(int row, int col, char val, vector<vector<char>>& board) { for (int i = 0; i < 9; i++) { // 1. 检查同一列是否有重复 if (board[i][col] == val) return false; // 2. 检查同一行是否有重复 if (board[row][i] == val) return false; // 3. 检查所在的 3x3 九宫格是否有重复 // 公式说明： // (row / 3) * 3 用于定位该点所属九宫格的“左上角”行坐标 // (col / 3) * 3 用于定位该点所属九宫格的“左上角”列坐标 // board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] 是更高级的写法， // 但你代码中原本的写法也很直观，如下： } // 定位当前格子所属的 3x3 九宫格的左上角起点 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; // 遍历这个 3x3 的小方格 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; // 完美，通过所有检查 }完整代码
class Solution { private: // 回溯核心函数：尝试填充棋盘，如果填满且有效返回 true，否则返回 false bool backtracking(vector<vector<char>>& board) { // 双重循环遍历整个棋盘（9x9） for (int i = 0; i < board.size(); i++) { // 遍历行 for (int j = 0; j < board[0].size(); j++) { // 遍历列 // 步骤 1: 寻找空白格（'.' 表示还没填数字） if (board[i][j] == '.') { // 步骤 2: 尝试填入数字 '1' 到 '9' for (char k = '1'; k <= '9'; k++) { // 步骤 3: 检查在 (i, j) 放数字 k 是否符合数独规则 if (isValid(i, j, k, board)) { board[i][j] = k; // 【做选择】：放置数字 k // 步骤 4: 递归调用 // 如果填入 k 之后，后续的递归也能成功填满棋盘，说明找到解了 if (backtracking(board)) return true; board[i][j] = '.'; // 【撤销选择】：回溯 // 如果上面的 backtracking 返回 false，说明刚才填 k 导致后面无解 // 所以要把 k 拿走，恢复成 '.'，以便下一次循环尝试 k+1 } } // 步骤 5: 关键点 // 如果 1-9 都试过了，都不合法（或者导致后续无解），说明当前这一步就死路一条 // 返回 false 给上一层递归，告诉它“你之前填的数有问题，换一个吧” return false; } } } // 步骤 6: 终止条件 // 如果双重循环跑完了，都没有遇到 return false，说明棋盘里没有 '.' 了（填满了） // 这就是我们想要的解，直接返回 true return true; } // 辅助函数：判断在 board[row][col] 填入字符 val 是否合法 bool isValid(int row, int col, char val, vector<vector<char>>& board) { for (int i = 0; i < 9; i++) { // 1. 检查同一列是否有重复 if (board[i][col] == val) return false; // 2. 检查同一行是否有重复 if (board[row][i] == val) return false; // 3. 检查所在的 3x3 九宫格是否有重复 // 公式说明： // (row / 3) * 3 用于定位该点所属九宫格的“左上角”行坐标 // (col / 3) * 3 用于定位该点所属九宫格的“左上角”列坐标 // board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] 是更高级的写法， // 但你代码中原本的写法也很直观，如下： } // 定位当前格子所属的 3x3 九宫格的左上角起点 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; // 遍历这个 3x3 的小方格 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; // 完美，通过所有检查 } public: void solveSudoku(vector<vector<char>>& board) { backtracking(board); } };
