你好，同学。今天我们要挑战搜索算法中的“珠穆朗玛峰”——数独求解 (Sudoku Solver)。

在 NOI 竞赛中，数独问题是典型的受限状态空间搜索。它不仅考察基础的回溯算法，更是练习“可行性剪枝”和“搜索顺序优化”的绝佳素材。

一、 题目描述 (NOI 风格)

题目名称：解数独 (Sudoku Solver) 时间限制：1.0s 内存限制：256MB

【问题描述】 编写一个程序，通过填充空格来解决数独问题。 一个数独的解法需遵循以下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用字符 . 表示。

【输入格式】 输入包含 9 行，每行包含 9 个字符，表示数独的初始状态。其中数字表示已填入的数，. 表示空格。

【输出格式】 输出 9 行，每行 9 个数字，表示完成后的数独网格。 题目保证输入数独仅有一个唯一解。

【样例输入】

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

【样例输出】

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

二、 预备知识点

1. 回溯法 (Backtracking)：尝试填入数字，若不合法则回退。
2. 二维数组状态维护：维护行、列、宫的占用情况。
3. 可行性剪枝 (Feasibility Pruning)：在递归前判断填入的数字是否符合三大规则。
4. 宫位索引转换：理解如何通过坐标 $(r, c)$ 计算其所属的 $3 \times 3$ 宫编号：idx = (r / 3) * 3 + c / 3。

三、 启发式思路引导：草稿纸上的推理

数独的搜索空间巨大（最多 $9^{81}$），必须在草稿纸上规划好每一步。

1. 状态判断的图形化思考

我们在填入数字 $d$ 到位置 $(r, c)$ 时，需要瞬时判断冲突。

• 行控制：row[r][d] 标记第 $r$ 行是否已有 $d$。
• 列控制：col[c][d] 标记第 $c$ 列是否已有 $d$。
• 宫控制：box[idx][d] 标记第 idx 宫是否已有 $d$。

2. 搜索逻辑演练

• 步骤 A：寻找下一个空格。如果找不到了，说明大功告成，返回 true。
• 步骤 B：在当前空格尝试填入 1 到 9。
• 步骤 C：检查该数字是否在对应的行、列、宫中出现过。
• 步骤 D：若不冲突，填入并递归。若递归返回 false（说明后面没解了），则清除当前填写的数字（回溯），尝试下一个数。

3. 搜索优化建议（提分关键）

• 顺序优化：在 NOI 考场上，不一定要按 $(0,0)$ 到 $(8,8)$ 的顺序搜。优先填备选数字最少的格子（即约束最强的格子），可以极大地压缩搜索树的规模。

四、 复杂度分析思考过程

• 时间复杂度：
  • 最坏情况下是指数级的。但数独规则极其严苛，合法分支很少。
  • 实际运行中，数独求解器通常在几毫秒到几十毫秒内完成。
• 空间复杂度：
  • 递归深度最大为 $81$。
  • 辅助标记数组（行、列、宫）占用空间极小，为 $O(1)$。

五、 算法流程图 (C++14 风格伪代码)

为了避免 Mermaid 语法解析错误，我们使用圆括号表示节点描述。

graph TD
    Start(开始搜索) --> FindBlank(寻找下一个空格 r-c)
    FindBlank -- 已填满 --> Found(找到唯一解 返回真)
    FindBlank -- 找到空格 --> LoopInit(循环数字 num 从 1 到 9)
    
    LoopInit --> CheckValid{检查 num 是否冲突}
    CheckValid -- 有冲突 --> NextNum(尝试下一个数字)
    CheckValid -- 无冲突 --> Fill(填入数字并更新行-列-宫状态)
    
    Fill --> Recur(递归调用 DFS 寻找下一个格)
    Recur -- 递归成功 --> Found
    Recur -- 递归失败 --> Backtrack(回溯 清除数字并恢复状态)
    
    Backtrack --> NextNum
    NextNum -->|循环结束| Fail(当前路径无解 返回假)

六、 读题关键词总结

1. “每一行/列/宫只能出现一次”：这是构造 used 标记数组的依据。
2. “唯一解”：意味着你搜到第一个解就可以直接一路 return true 退出，不需要搜全集。
3. “3x3 宫”：这是解题的难点，需要熟练掌握坐标到宫索引的映射公式。
4. “.” 代表空格：提醒你在读取输入时要进行字符处理。

教练寄语： 数独是搜索中的经典。初学者容易迷失在多重循环里，而高手则擅长利用位运算（用一个 int 的 9 位二进制表示数字占用情况）来进一步优化。先稳稳地写出基于布尔数组的回溯，再考虑性能优化。加油！