5910: 【系列题】回溯(十五)解数独

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考样例说明)

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


Input

共9行字符串。

每行9个字符。

空白格用 '.' 表示

Output

数独的答案。

也是9行,每行9个数字。

Sample Input Copy

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

Sample Output Copy

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

HINT

样例说明:

 

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

 


数据范围:

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