一、题目背景
本题为2020年省赛程序设计题
- C/C++ C 组第8题
二、题目描述
1.问题描述
小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3 x 3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。
4 9 2
3 5 7
8 1 6有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。而你，也被小明交付了同样的任务，但是不同的是，你需要写一个程序。
2.输入格式
输入仅包含单组测试数据。
每组测试数据为一个3 x 3的矩阵，其中为0的部分表示被小明抹去的部分。
对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。
3.输出格式
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。
4.一个例子
| 下面是一个样例 |
输入：
0 7 2
0 5 0
0 3 0输出：
6 7 2
1 5 9
8 3 4三、题目分析
1. 执果索因
通过使用科技的力量或者自己独立思考，提前找出三阶幻方的所有可能解。
再将自己已经知道的所有解提前放入程序里面，与输入的数进行比对。
如果只能比对出一组可行的幻方，则将其输出。
科技力量直通车→科技创造美好生活
2. 全排列
上面的方法是将已知答案放入程序中，但是更多的情况，我们是不知道答案的。
对此，我们只能将所有可能都弄出来。
这里就需要利用数学中的排列知识了。
排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。
而C++ 的algorithm中提供了内置的全排列函数next_permutation
下面介绍一下next_permutation函数
使用方法：next_permutation(数组头地址，数组尾地址);
若下一个排列存在，则返回真，如果不存在则返回假
举个例子：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int b[3] = { 1,2,3 };
do
{
for (int i = 0; i < 3; ++i)
cout << b[i] ;
cout << endl;
} while (next_permutation(b, b + 3));
return 0;
}
利用循环，和next_permutation的返回值，巧妙的得到全排列结果。
然后利用九宫幻方的性质，检查是不是九宫幻方。
九宫幻方：每一行、每一列、每一对角线的和都相同。
3. 深度优先搜索（DFS）
注意：完全不知道DFS是什么的可以看下这篇博客：深度优先搜索（DFS）
四、代码汇总
1. 执果索因
#include <iostream>
#include<string>
#include <algorithm>
using namespace std;
int main()
{
int a[3][3], f = 0, k = 0, i, j;
//初始化
string b = "000000000";
//所有可能的答案
string vis[8] = { "816357492","618753294","492357816","294753618","672159834","834159672","276951438","438951276" };
int v[8] = { 0 };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> a[i][j];
//将int转为string
b[k++] = a[i][j] + '0';
}
}
for (i = 0; i < 8; i++)
{
for (j = 0; j < 9; j++)
{
if (b[j] != '0')
{
//比较下一个字符串
if (vis[i][j] != b[j])
break;
}
}
if (j == 9)
{
f++;
v[i] = 1;
}
if (f > 1)
{
cout << "Too Many" << endl;
break;
}
}
k = 0;
if (f == 1)
{
for (i = 0; i < 9; i++)
if (v[i] == 1)break;
while (k < 9)
{
cout << vis[i][k++] << " ";
if (k % 3 == 0)cout << endl;
}
}
return 0;
}
2. 全排列
#include <iostream>
#include<string>
#include <algorithm>
using namespace std;
int arr[9];
int str[9] = { 1,2,3,4,5,6,7,8,9 };
bool flag = true;
int ans = 0;
//检查是不是九宫幻方
bool check(int a[])
{
int a1 = a[0] + a[1] + a[2];
int a2 = a[3] + a[4] + a[5];
int a3 = a[6] + a[7] + a[8];
int a4 = a[0] + a[3] + a[6];
int a5 = a[1] + a[4] + a[7];
int a6 = a[2] + a[5] + a[8];
int a7 = a[2] + a[4] + a[6];
int a8 = a[0] + a[4] + a[8];
if (a1 == a2 && a2 == a3 && a3 == a4 && a4 == a5 && a5 == a6 && a6 == a7 && a7 == a8)
return true;
return false;
}
int main()
{
for (int i = 0; i < 9; i++)
cin >> arr[i];
do {
if (check(str))
{
flag = true;
for (int i = 0; i < 9; i++)
{
if (arr[i] != 0 && arr[i] != str[i])
{
flag = false;
}
}
if (flag)
{
for (int i = 0; i < 9; i++)
arr[i] = str[i];
ans++;
}
}
} while (next_permutation(str, str + 9));
if (ans == 1)
{
int k = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cout << arr[k] << " ";
k++;
}
cout << endl;
}
}
else if (ans > 1)
cout << "Too Many" << endl;
return 0;
}3. DFS
#include <iostream>
#include<string>
#include <algorithm>
int a[5][5];
int b[5][5];
int vis[15];
int ans = 0;
using namespace std;
bool check()
{
int sum1, sum2;
int x = a[1][1] + a[1][2] + a[1][3];
for (int i = 1; i <= 3; i++)
{
sum1 = 0, sum2 = 0;
for (int j = 1; j <= 3; j++)
{
sum1 += a[i][j];
sum2 += a[j][i];
}
if (sum1 != x || sum2 != x)
return 0;
}
sum1 = a[1][1] + a[2][2] + a[3][3];
sum2 = a[1][3] + a[2][2] + a[3][1];
if (sum1 != x || sum2 != x)
return false;
return true;
}
void dfs(int num)
{
if (num == 9)
{
if (check())
{
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
b[i][j] = a[i][j];
ans++;
}
return;
}
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
{
if (a[i][j] == 0)
{
for (int k = 1; k <= 9; k++)
{
if (!vis[k])
{
vis[k] = 1;
a[i][j] = k;
dfs(num + 1);
vis[k] = 0;
a[i][j] = 0;
}
}
return;
}
}
}
int main()
{
int num = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
{
cin >> a[i][j];
vis[a[i][j]] = 1;
if (a[i][j] != 0)
num++;
}
dfs(num);
if (ans == 1)
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
cout << b[i][j] << " ";
cout << endl;
}
else
cout << "Too Many" << endl;
return 0;
}
五、总结
1. 全排列
排列、全排列的计算。
全排列函数：next_permutation 的用法。
2. 九宫幻方的判断
九宫幻方：每一行、每一列、每一对角线的和都相同。
