3041. 数独【剪枝优化】
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 数独是一种传统益智游戏，你需要把一个$9\times9$ 的数独补充完整，使得数独中每行、每列、每个 $3\times3$ 的九宫格内数字 $1∼9$ 均恰好出现一次。 请编写一个程序填写数独。  ## 输入格式 输入包含多组测试用例。 每个测试用例占一行，包含$81$ 个字符，代表数独的 $81$ 个格内数据（顺序总体由上到下，同行由左到右）。 每个字符都是一个数字（$1-9$）或一个 `.`（表示尚未填充）。 **您可以假设输入中的每个谜题都只有一个解决方案。** 文件结尾处为包含单词 `end` 的单行，表示输入结束。 ## 输出格式 每个测试用例，输出一行数据，代表填充完全后的数独。 ## 输入 ```in1 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. end ``` ## 输出 ```out1 417369825632158947958724316825437169791586432346912758289643571573291684164875293 416837529982465371735129468571298643293746185864351297647913852359682714128574936 ``` ## 提示