J10 例题-2 数独

题目描述

编写一个程序，通过已填充的空格来解决数独问题。 一个数独的解法需遵循如下规则： 数字 $1-9$ 在每一行只能出现一次。 数字 $1-9$ 在每一列只能出现一次。 数字 $1-9$ 在每一个以粗实线分隔的 $3 \times 3$ 宫内只能出现一次。 空白格用 0 表示。

输入格式

一个 $9 \times 9$ 的矩阵，同一行相邻的两个元素用一个空格分开。其中 $1-9$ 代表该位置的已经填好的数， 0 表示需要你填的数。

输出格式

请输出它的解，同一行相邻的两个数用一个空格分开。 数据保证它有且只有一个解。

样例输入

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

样例输出

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

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有：保证有且只有一个解。