166. 数独

数独是一种传统益智游戏,你需要把一个9 × 9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行,包含81个字符,代表数独的81个格内数据(顺序总体由上到下,同行由左到右)。

每个字符都是一个数字(1-9)或一个”.”(表示尚未填充)。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词“end”的单行,表示输入结束。

输出格式

每个测试用例,输出一行数据,代表填充完全后的数独。

输入样例:

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

输出样例:

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936