1.九宮幻方 - 藍橋云課

九宮幻方

題目描述

小明最近在教鄰居家的小朋友小學奧數，而最近正好講述到了三階幻方這個部分，三階幻方指的是將1~9不重復的填入一個3 * 3的矩陣當中，使得每一行、每一列和每一條對角線的和都是相同的。

三階幻方又被稱作九宮格，在小學奧數里有一句非常有名的口訣：“二四為肩，六八為足，左三右七，戴九履一，五居其中”，通過這樣的一句口訣就能夠非常完美的構造出一個九宮格來。

492
357
816

有意思的是，所有的三階幻方，都可以通過這樣一個九宮格進行若干鏡像和旋轉操作之后得到。現在小明準備將一個三階幻方（不一定是上圖中的那個）中的一些數抹掉，交給鄰居家的小朋友來進行還原，并且希望她能夠判斷出究竟是不是只有一個解。

而你呢，也被小明交付了同樣的任務，但是不同的是，你需要寫一個程序。

輸入描述

輸入僅包含單組測試數據。

每組測試數據為一個3 * 3的矩陣，其中為0的部分表示被小明抹去的部分。

給出的矩陣至少能還原出一組可行的三階幻方。

輸出描述

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

輸入輸出樣例

??示例??

??輸入??

0 7 2
0 5 0
0 3 0

??輸出??

6 7 2
1 5 9
8 3 4

思路：

題目要求，只有一個解那么久輸出這個解，如果多個解就輸出too many。所以我們需要用一個數組儲存第一個解。（題目說了輸入數據會有解的）。

1.因為我們要填空，但是這個二維數組的填空有點麻煩，所以我們可以將每一個需要填空的位置記錄在一個一維數組里面，這樣就比較好爆搜了。

2.利用桶思維保證每一個數字只出現一次

3.check函數檢查

代碼如下：

#include <bits/stdc++.h>
using namespace std;struct Node{int x, y; }pos[10];//儲存位置的數組 
int a[4][4], res[4][4];
bool used[10]; 
int cnt, ans;
bool check()
{for(int i = 1 ; i <= 3 ; i++)//判斷行和列 {int s_row = a[i][1] + a[i][2] + a[i][3];int s_rank = a[1][i] + a[2][i] + a[3][i];if(s_row != 15 || s_rank != 15)return false;	}int s_pd = a[1][1] + a[2][2] + a[3][3];int s_nd = a[1][3] + a[2][2] + a[3][1];if(s_pd != 15 || s_nd != 15)return false;return true; 
}
void dfs(int step) 
{if (ans > 1) return; // 發現多解立即終止if (step > cnt) {if (check()) {ans++;if (ans == 1) // 僅保存第一個解{for(int i = 1 ; i <= 3 ; i++){for(int j = 1 ; j <= 3 ; j++){res[i][j] = a[i][j];				}		   	}	}}return;}int x = pos[step].x, y = pos[step].y;//取出坐標 for (int i = 1; i <= 9; i++) {if (!used[i]) {used[i] = true;a[x][y] = i;dfs(step + 1);used[i] = false;a[x][y] = 0; // 回溯}}
}
int main() 
{for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {cin >> a[i][j];if (a[i][j] == 0) {++cnt;pos[cnt].x = i; // 從1開始記錄待填位置pos[cnt].y = j;} else {used[a[i][j]] = true; // 標記已用數字}}}dfs(1);if (ans == 1) {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {cout << res[i][j] << " ";}cout << endl;}} else {cout << "Too Many";}return 0;
}

思路：

二維數組寫法，直接模擬x,y負責填數字即可

代碼：

#include <bits/stdc++.h>
using namespace std;struct Node{int x, y; }pos[10];//儲存位置的數組 
int a[4][4], res[4][4];
bool used[10]; 
int cnt, ans;
bool check()
{for(int i = 1 ; i <= 3 ; i++)//判斷行和列 {int s_row = a[i][1] + a[i][2] + a[i][3];int s_rank = a[1][i] + a[2][i] + a[3][i];if(s_row != 15 || s_rank != 15)return false;	}int s_pd = a[1][1] + a[2][2] + a[3][3];int s_nd = a[1][3] + a[2][2] + a[3][1];//對角線 if(s_pd != 15 || s_nd != 15)return false;return true; 
}
void dfs(int x,int y) 
{if (ans > 1) return; // 發現多解立即終止if(y > 3){x++;y = 1;}   if (x > 3) {if (check()) {ans++;if (ans == 1) // 僅保存第一個解{for(int i = 1 ; i <= 3 ; i++){for(int j = 1 ; j <= 3 ; j++){res[i][j] = a[i][j];				}		   	}	}}return;}if(a[x][y] == 0){for(int i = 1 ; i <= 9 ; i++){if (!used[i]) {used[i] = true;a[x][y] = i;dfs(x,y+1);used[i] = false;a[x][y] = 0; // 回溯}}}else{dfs(x,y+1);}}
int main() 
{for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {cin >> a[i][j];if(a[i][j] > 0)used[a[i][j]] = true; }}dfs(1,1);if (ans == 1) {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {cout << res[i][j] << " ";}cout << endl;}} else {cout << "Too Many";}return 0;
}