14010 - 九宫幻方

通过次数

7

提交次数

15

时间限制 : 1 秒
内存限制 : 256 MB

小明在教邻居家的小朋友小学奥数,最近讲到了三阶幻方(九宫格)。三阶幻方是将数字 1~9 不重复地填入一个 3×3 的矩阵中,使得每行、每列以及两条对角线的和都相等(均为 15)。

经典的九宫格如:

4 9 2

3 5 7

8 1 6

所有三阶幻方都可以通过上述基本幻方经过旋转(0°、90°、180°、270°)和镜像(水平翻转)得到,共 8 种。

现在小明将一个三阶幻方中的某些数字抹掉(用 0 表示),请你编写程序判断:能否唯一确定被抹掉的数字,从而还原出完整的幻方。

  • 如果仅有一种可能的完整幻方,则输出该幻方;
  • 如果有多种可能,则输出 Too Many

题目保证输入至少存在一组可行的完整幻方。

输入

输入仅包含一组测试数据,为一个 3 \times 3 的整数矩阵,其中 0 表示被抹去的数字,其他数字表示已知数字。

输出

  • 若仅能还原出一组可行幻方,则输出该幻方,每行三个数字,数字之间用空格隔开。
  • 否则输出一行 Too Many(不含引号)。

样例

输入

0 7 2
0 5 0
0 3 0

输出

6 7 2
1 5 9
8 3 4

提示

数据范围与约定

  • 输入保证至少有一组可行解。
  • 数字范围 0~9,且 0 表示空格。

提示

三阶幻方一共只有 8 种,可以直接枚举所有可能,逐一与输入进行匹配,统计符合条件的数量。若数量为 1,则输出该幻方;否则输出 Too Many

来源

蓝桥杯