[藍橋杯2017初賽]九宮幻方

小明最近在教鄰居家的小朋友國小奧數，而最近正好講述到了三階幻方這個部分。

三階幻方指的是将1~9不重複的填入一個33的矩陣當中，使得每一行、每一列和每一條對角線的和都是相同的。

三階幻方又被稱作九宮格，在國小奧數裡有一句非常有名的口訣：

“二四為肩，六八為足，左三右七，戴九履一，五居其中”，

通過這樣的一句口訣就能夠非常完美的構造出一個九宮格來。

4 9 2

3 5 7

8 1 6

有意思的是，所有的三階幻方，都可以通過這樣一個九宮格進行若幹鏡像和旋轉操作之後得到。

現在小明準備将一個三階幻方（不一定是上圖中的那個）中的一些數抹掉，交給鄰居家的小朋友來進行還原，并且希望她能夠判斷出究竟是不是隻有一個解。

而你呢，也被小明傳遞了同樣的任務，但是不同的是，你需要寫一個程式~

輸入

輸入一個33的矩陣，其中為0的部分表示被小明抹去的部分。

對于100%的資料，滿足給出的矩陣至少能還原出一組可行的三階幻方。

輸出

如果僅能還原出一組可行的三階幻方，則将其輸出，否則輸出“Too Many”（不包含引号）。

樣例輸入 Copy

0 7 2

0 5 0

0 3 0

樣例輸出 Copy

6 7 2

1 5 9

8 3 4

全排列比對,對1 ~9 ,9個數進行全排列，當遇到原數組有不為0的，并且與排列的數不同的，說明不滿足要求，continue

#include <iostream>
#include <algorithm>
using namespace std;
int a[10] = {1,2,3,4,5,6,7,8,9};
int b[10],temp[10],t[10];
int cnt;
int main()
{
	for (int i =0 ; i < 9 ; i ++)  cin >> b[i];
	
	do
	{
		bool flag1 =false;
		for (int i = 1; i <= 9 ; i ++)
		{
			if (b[i] && b[i] != a[i])
			{
				flag1 = true;
				break;
			}
		}
		if (flag1) continue;
		
    	int x1 =a[0] + a[1] + a[2];
        int x2 =a[3] + a[4] + a[5];
        int x3 =a[6] + a[7] + a[8];
 
        int y1 =a[0] + a[3] + a[6];
        int y2 =a[1] + a[4] + a[7];
        int y3 =a[2] + a[5] + a[8];
 
        int m = a[0] + a[4] + a[8];
        int n = a[2] + a[4] + a[6];
        if(x 1== x2 && x2 == x3)
        {
            if(x3 == y1 && y1 == y2 && y2 == y3)
            {
                if(y3 == m && m == n)
                {
                    cnt ++;
                    for(int i = 0 ; i < 9 ; i ++)
                        temp[i] = a[i];
                }
            }
        }
		
	}while (next_permutation(a,a + 9));
	if (cnt == 1)
	{
		for (int i = 0 ; i < 9 ; i ++)
		{
			cout << temp[i] << ' ';
			if ((i + 1) % 3 == 0) cout << endl;
		}
	}
	else puts("Too Many");
	return 0;
}

           

DFS:

把9個數讀入到a[i]中去，每讀入一個數，就标記一下這個數是否為0，是否使用過；

dfs(1)從第一個位置還是深搜，

如果cnt > 1，傳回，如果st[x]這個位置的數不為0,不用填數字，dfs下一層;

枚舉1~9,9個數，如果這個數沒有被用過，就把這個數填進去；

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;
int a[N],b[N],ans[N];
bool st[N],used[N];
int cnt;
void check()
{
	b[1] = a[1] + a[2] + a[3];
	b[2] = a[4] + a[5] + a[6];
	b[3] = a[7] + a[8] + a[9];
	b[4] = a[1] + a[4] + a[7];
	b[5] = a[2] + a[5] + a[8];
	b[6] = a[3] + a[6] + a[9];
	b[7] = a[1] + a[5] + a[9];
	b[8] = a[3] + a[5] + a[7];
	
	for (int i = 1 ; i <= 8 ; i ++)  if (b[i] != 15) return;
	
	cnt ++;
	for (int i = 1 ; i <= 9 ; i ++)  ans[i] = a[i];
}
void dfs(int x) //目前在第x個位置
{
	if (cnt > 1) return;
	if (x > 9)
	{
		check();
		return;
	}
	if (st[x]) //目前這個位置已經有不為0的數字 
	{
		dfs(x + 1);
		return;
	}
	for (int i = 1 ; i <= 9 ; i ++)
	{
		if (!used[i])
		{
			a[x] = i;
			used[i] = true;
			dfs(x + 1);
			used[i] = false;
		}
	} 
} 
int main()
{
	for ( int i = 1 ; i <= 9 ; i ++)
	{
		cin >> a[i];
		if (a[i])
		{
			st[i] = true;//标記i這個位置的數不為0
			used[a[i]] = true; //标記a[i]這個數已經被用過 
		}
	}
	dfs(1);//從第一個位置開始深搜 
	
	if (cnt == 1)
	{
		for (int i = 1;  i <= 9 ; i ++)
		{
			cout << ans[i] <<' ';
			if (i % 3 == 0) cout << endl;
		}
	}
	else puts("Too Many");
	return 0;
}