数据结构与算法专题题库

1021. 数独问题

单点时限: 2.0 sec

内存限制: 512 MB

给定一个不完整的数独,要求将数独中空白的部分用19的数字填充。

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

  • 数字19在每一行只能出现一次。
  • 数字19在每一列只能出现一次。
  • 数字19在每一个以粗实线分隔的3×3宫内只能出现一次。

下图为一个简单的数独:

下图为上面数独的解。

输入格式

输入9行,每行9个字符,空格用.表示。

输出格式

输出9行,每行9个字符,如果有多解,输出字典序最小的解。

其中字典序定义为将数独按照行优先比较,即假设两个数独a和数独b,如果前i行都一样,
则按照第i+1行的字典序大小决定两个数独的大小。

样例

Input
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Input
534678...
6..19534.
1983..567
85.761.23
426853..1
7..924856
961..7284
287419635
..5286179
Output
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

提示

对于30%数据满足:数独中最多7个空格。

对于70%数据满足:数独保证有唯一解。

对于100%数据满足:数独不保证有唯一解。

不限期开放

题目列表