#222210. [2023第十四届蓝桥杯国赛T4] 数独填数

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Krist

题目描述

本题数据有放水,普通的爆搜也给通过了。有兴趣的同学可以自行测试,下方附加的额外数据。

数独是源自 18 世纪瑞士的一种数学游戏。玩家需要根据 9×9 网格上的已知数字,将剩余的所有空格填上数字,使得 9×9 网格上每一行、每一列及每一个 3×3 方块 (粗线)内的数字均包含 1~9,并且数字不重复。

例1:下图 (左) 是未完成的数独,下图 (右)是完成后的结果。

这个数独可以使用如下 9×9 的字符方阵表示 (空格用 "." 表示)。

17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734

现在给定一道数独题,请编程完成填数,并输出最后的结果。

输入格式

共有 9 行,表示未完成的数独。

每一行包含 9 个字符(字符只能为 1~9 的数字和 "."),字符之间没有空格及其他字符。

其中 "." 表示数独上的空格。题目数据保证数独有效且答案唯一。

输出格式

输出 9 行,表示已完成的数独每行 9 个数字,数字之间没有空格及其他字符。

样例

17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734

数据范围与提示

附加一组卡掉不加优化爆搜的数据,请同学们有兴趣进行自测。

【输入】

9..8.....
......5..
.........
.2..1...3
.1.....6.
...4...7.
7.86.....
....3.1..
4.....2..

【输出】

972853614
146279538
583146729
624718953
817395462
359462871
798621345
265934187
431587296