题目:

小Hi最近在教邻居家的小朋友小学奥数,而最近正好讲述到了三阶幻方这个部分,三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中,使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格,在小学奥数里有一句非常有名的口诀:“二四为肩,六八为足,左三右七,戴九履一,五居其中”,通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

有意思的是,所有的三阶幻方,都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方(不一定是上图中的那个)中的一些数组抹掉,交给邻居家的小朋友来进行还原,并且希望她能够判断出究竟是不是只有一组解。

而你呢,也被小Hi交付了同样的任务,但是不同的是,你需要写一个程序~

Input

输入仅包含单组测试数据。

每组测试数据为一个3*3的矩阵,其中为0的部分表示被小Hi抹去的部分。

对于100%的数据,满足给出的矩阵至少能还原出一组可行的三阶幻方。

Output

如果仅能还原出一组可行的三阶幻方,则将其输出,否则输出“Too Many”(不包含引号)。

Sample Input

0 7 2
0 5 0
0 3 0

Sample Output

6 7 2
1 5 9
8 3 4

思路分析:这种题一看就知道是搜索,而且一般用深搜DFS。但是这里有一个小小的技巧。因为这个题只是一个3 x 3的矩阵,如果在DFS过程中有的是二位矩阵并不方便限定搜索终止条件,所以完全可以用一个一维矩阵来代替这个二维矩阵。

#include <bits/stdc++.h>
using namespace std;

int vis[10];
int mp[10];
int mp2[10];
int cnt = 0;

bool isok()
{
	vector<int> v;
	v.clear();
	int sum;
	sum = mp[1] + mp[2] + mp[3];	// 1 行
	v.push_back(sum);
	sum = mp[4] + mp[5] + mp[6];	// 2 行
	v.push_back(sum);
	sum = mp[7] + mp[8] + mp[9];   // 3
	v.push_back(sum);
	sum = mp[1] + mp[4] + mp[7];	// 1列
	v.push_back(sum);
	sum = mp[2] + mp[5] + mp[8];	// 2
	v.push_back(sum);
	sum = mp[3] + mp[6] + mp[9];	// 3
	v.push_back(sum);
	sum = mp[1] + mp[5] + mp[9];	// 主对角线
	v.push_back(sum);
	sum = mp[3] + mp[5] + mp[7];	// 副对角线
	v.push_back(sum);
	sort(v.begin(), v.end());
	int n = v.size();
	if( v[0] == v[n-1] )
		return true;
	else
		return false;
}

void dfs( int x )
{
	if( x == 10 && isok() )
	{
		cnt ++;
		if( cnt == 1 )
			for( int i=1; i<=9; i++ )
				mp2[i] = mp[i];
		return ;
	}
	if( mp[x] )
		dfs(x+1);
	else
	{
		for( int i=1; i<=9; i++ )	// 九个数都试一下能否用
		{
			if( vis[i] )
				continue;
			vis[i] = 1;
			mp[x] = i;
			dfs(x+1);
			vis[i] = 0;		// 回溯
			mp[x] = 0;
		}
	}

}
int main()
{
	memset(vis, 0, sizeof(vis));
	for( int i=1; i<=9; i++ )
	{
		scanf("%d", &mp[i]);
		vis[mp[i] ] = 1;
	}
	cnt = 0;
	dfs(1);
	if( cnt == 1 )
	{
		for( int i=1; i<=9; i++ )
		{
			printf("%d%c", mp2[i], (i%3) == 0 ? '\n' : ' ');	// 输出技巧
		}
	}
	else
		printf("Too Many\n");



	return 0;
}