题目描述

用深度优先搜索（DFS）填充9×9数独，保证唯一解。

输入格式

一个9×9的数独网格，其中0表示空格，1-9表示已填数字（需满足数独规则）。

输出格式

填充完成的数独网格（唯一解），或提示无解。

样例

输入样例 1

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

输出样例 1

数独解：
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
---------------------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
---------------------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

输入样例 2

0 2 0 6 0 8 0 0 0
5 8 0 0 0 9 7 0 0
0 0 0 0 4 0 0 0 0
3 7 0 0 0 0 5 0 0
6 0 0 0 0 0 0 0 4
0 0 8 0 0 0 0 1 3
0 0 0 0 2 0 0 0 0
0 0 9 8 0 0 0 3 6
0 0 0 3 0 6 0 9 0

输出样例 2

数独解：
1 2 3 | 6 7 8 | 9 4 5
5 8 4 | 2 3 9 | 7 6 1
9 6 7 | 1 4 5 | 3 2 8
---------------------
3 7 2 | 4 6 1 | 5 8 9
6 9 1 | 5 8 3 | 2 7 4
4 5 8 | 7 9 2 | 6 1 3
---------------------
8 3 6 | 9 2 4 | 1 5 7
2 1 9 | 8 5 7 | 4 3 6
7 4 5 | 3 1 6 | 8 9 2

输入样例 3

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

输出样例 3

数独解：
1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
---------------------
2 1 4 | 3 6 5 | 8 9 7
3 6 5 | 8 9 7 | 2 1 4
8 9 7 | 2 1 4 | 3 6 5
---------------------
5 3 1 | 6 4 2 | 9 7 8
6 4 2 | 9 7 8 | 5 3 1
9 7 8 | 5 3 1 | 6 4 2

提示

解题思路：1.数独规则：每行、每列、每个3×3宫格内数字1-9不重复。 2.DFS核心逻辑：遍历数独网格，找到第一个空格（值为0）。尝试填入1-9中未被当前行、列、宫格使用的数字，递归填充下一个空格。若填入后无解，则回溯（撤销当前选择），尝试下一个数字。