回溯法解数独的核心逻辑是边填边检查约束并及时剪枝：对每个空格尝试1–9，调用isValid高效验证行列宫格是否冲突，失败则回退；递归结构以查找空格为起点，成功返回true，失败还原后继续试数。
回溯法解数独的核心逻辑是什么
数独求解的本质是约束满足问题：每行、每列、每个 3×3 宫格都必须填入 1–9 且不重复。回溯法在这里不是“暴力试所有排列”，而是边填边检查，一旦发现当前填法违反规则，立刻退回上一步——这能剪掉大量无效分支。
关键判断点在于：isValid(board, row, col, c) 必须高效检查三个维度（行、列、宫格）是否已存在数字 c；而主递归函数通常以「找空格→试数字→递归填下一个空→失败则还原」为循环结构。
如何写一个高效的 isValid 检查函数
常见错误是每次检查都遍历整行、整列、整个宫格，导致时间复杂度飙升。实际只需遍历对应行的 9 列、对应列的 9 行、对应宫格的 9 个位置即可。
更优做法是用三个布尔数组预存状态（但注意：若需支持多次调用或重置，得在回溯外初始化）；不过对单次求解，直接检查更清晰、无副作用：
立即学习“C++免费学习笔记（深入）”；
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == c || board[i][col] == c) return false;
}
int boxRow = (row / 3) * 3, boxCol = (col / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[boxRow + i][boxCol + j] == c) return false;
}
}
return true;
}- 注意整除取宫格起始坐标用
(row / 3) * 3，不是row / 3直接当索引 -
board是vector<vector>></vector>，空格用'.'表示，数字是字符'1'–'9'，别和整数 1–9 混用 - 检查顺序建议先行列再宫格，因行列冲突概率更高，早返回能省计算
solveSudoku 的递归结构怎么组织
标准写法是「找下一个空格」作为递归入口，而不是按 (0,0)→(0,1)→… 固定遍历。这样避免重复扫描已填位置，也便于提前终止。
函数通常返回 bool：成功填完返回 true，失败则还原并返回 false。关键点在于：只有递归调用返回 true 才向上透传，否则必须撤回当前填写（即 backtracking 的“back”动作）：
bool solveSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
for (char c = '1'; c <= '9'; c++) {
if (!isValid(board, i, j, c)) continue;
board[i][j] = c;
if (solveSudoku(board)) return true;
board[i][j] = '.'; // 必须还原！
}
return false; // 9 个数字全试过都不行，此路不通
}
}
return true; // 没找到空格，说明填完了
}- 内层
for (char c = '1'; ...)是试数，不是int c = 1；字符比较才匹配board中的值 - 还原语句
board[i][j] = '.'必须写在if (solveSudoku(...))之后、return false之前——漏掉就变成污染状态，后续调用全错 - 最外层循环结束直接
return true，代表无空格可填，即完成
为什么有些数独死循环或返回 false
典型原因不是算法错，而是输入或边界处理疏忽：
- 输入
board含非法字符（如空格、'0'、大写字母），isValid可能没做防御，导致逻辑跳过或越界 - 初始棋盘本身矛盾（比如同一行有两个 '5'），但代码没做预检，回溯过程中永远卡在某个位置反复尝试
- 递归未设终止条件，或空格查找逻辑有 bug（例如跳过最后一行），造成无限递归或栈溢出
- 编译器优化或调试器干扰可能掩盖变量未初始化问题，建议在
solveSudoku开头加一句if (board.empty()) return false;防空输入
真正难调的点往往不在回溯框架，而在字符/整数混淆、坐标算错宫格、忘记还原——这些地方多打两行 cout 就能定位。
