题目描述

这个游戏只有一个规则：将格子填满使得每一行、每一列，和每一个小的 3×3 九宫格恰好包含 1-9 这 9 个数字。正是由于规则简单而又变化多端，数独一时间风靡全球。现在，我们希望你能编写一个程序解决数独问题。

输入格式

输入数据一共 9 行，每行有 9 个字符。输入数据描述了一个待解决的数独，其中，? 表示数独中的空缺。我们的输入数据总保证有唯一解。

输出格式

输出一共 9 行，每行 9 个数字，表示你的答案。

样例 #1

样例输入 #1

5????7??6
?6????5?4
?834?????
???182?4?
??1???9??
?7?369???
?????543?
1?5????9?
7??2????1

样例输出 #1

514927386
967831524
283456179
659182743
321574968
478369215
892615437
135748692
746293851

样例解释 #1

输入的数独中存在多个空缺（用 ? 表示），根据数独规则（每行、每列、每个 3×3 小九宫格包含 1-9 且不重复），可以唯一确定每个空缺位置的数字。输出即为填充后的完整数独，满足所有规则。