回溯法解决数独和八皇后问题的核心是“试错+撤回”：聚焦空位或每行，用布尔数组o(1)校验约束，即时剪枝，递归前后成对修改与恢复状态，避免贪心或dp的局限性。
回溯法解决数独和八皇后问题，核心都是“试错+撤回”：在每一步尝试合法选项，一旦发现冲突立即退回上一步换方案，直到填满或穷尽所有可能。
数独求解的关键操作
数独是9×9网格，需满足行、列、3×3宫格内1–9不重复。回溯时不是盲目填数，而是聚焦空白格，逐个试探：
- 先遍历整个棋盘，收集所有空位坐标（如(i, j)），避免每次递归都扫描全表
- 对当前空位，依次尝试1到9；用三个布尔数组快速判断该数字是否已在同行、同列、同宫格出现（预处理行/列/宫格占用状态，比实时遍历快得多）
- 若某数字合法，填入并递归处理下一个空位；若后续无解，就清空该格（回溯），继续试下一个数字
- 当所有空位填完，即得唯一解（题目保证有解）
八皇后问题的结构化建模
八皇后本质是排列问题：每行放且仅放一个皇后，关键在于列和对角线约束。高效实现依赖状态压缩：
- 用一维数组queens[i] = j表示第i行皇后放在第j列，天然避免同行冲突
- 列冲突用布尔数组cols[j]标记；主对角线（r−c为定值）用diag1[r−c+7]（加偏移防负索引）；副对角线（r+c为定值）用diag2[r+c]
- 从第0行开始递归，每行遍历8列，检查列与两条对角线是否空闲；可行则标记并进入下一行；返回时清除标记
两个问题的共性设计要点
尽管场景不同，但回溯框架高度一致：
- 解空间定义：数独是二维填空序列，八皇后是一维列位置排列——选择合适的数据结构简化状态管理
- 约束即时校验：不在填完才验证，而是在放置前用O(1)时间判断（靠预维护的布尔数组或集合）
- 剪枝是关键：无效分支越早终止越好。例如数独中某空位试遍1–9全冲突，立刻回退；八皇后中某行无合法列，直接返回上层
- 原地修改+恢复：所有状态变更（填数、标记数组）必须在递归前后成对出现，确保回溯后环境干净
为什么不用其他算法？
贪心法会失败——局部填最小可用数可能导致后续无解；动态规划不适用，因填数决策有强后效性（当前选择直接影响后续可行性）；而回溯配合剪枝，能在实际规模内高效收敛，是这类约束满足问题的标准解法。
