Description

数独是一种经典的填数游戏：给定一个 9×9 的棋盘，其中部分格子已经填入了 1~9 的数字，其余格子为空。

要求填入数字，使得：

1. 每一行都恰好包含数字 1~9 各一次；
2. 每一列都恰好包含数字 1~9 各一次；
3. 每一个 3×3 的小宫（共有 9 个）都恰好包含数字 1~9 各一次。

我们用字符 '.' 表示空格，用字符 '1'~'9' 表示已经填好的数字。

现在给定一个有唯一解的数独盘面，请你求出任意一个完整解，并将整个 9×9 棋盘输出。

Input Format

输入共 9 行，每行是一个长度为 9 的字符串，仅包含 '.' 或 '1'~'9'，表示数独初始盘面。

保证至少存在一种完整解，并且解的数量为 1（唯一解）。

Output Format

输出 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

（注意：以上只是示例，实际测试数据中会包含多组不同的数独。）

Source

DFS 深度优先搜索（数独求解器）