Sudoku_牛客题霸

数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含这九个数字，且不重复。保证输入的数独是合法的，且存在唯一解。

输入描述:

输入一个 的不完整数独矩阵，矩阵中的数字为 。其中， 表示该位置的数字尚未填入， 表示该位置的数字已经填入。

输出描述:

输出一个 的完整数独矩阵。

示例1

输入

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

输出

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

说明

在这个样例中，输入的数独如下图一所示，输出的是数独的唯一解，如下图二所示。