#HS015. 解数独

解数独

说明

编写一个程序,通过填充空格来解决数独问题。 数独的解法需 遵循如下规则:

  • 数字 191\sim9 在每一行只能出现一次;
  • 数字 191\sim9 在每一列只能出现一次;
  • 数字 191\sim9 在每一个以粗实线分隔的 3×33\times3 宫格内只能出现一次。(请参考样例说明)

数独部分空格内已填入了数字,空白格用 . 表示。

输入

99 行字符串; 每行 99 个字符; 空白格用 . 表示。

输出

数独的答案,也是 99 行,每行 99 个数字。

样例

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

提示

样例说明

image

解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

image

数据范围

  • 题目数据 保证 输入数独仅有一个解。