【解题报告+通法】_九宫幻方 蓝桥杯 2017年C组第八题（dfs解法）

题目描述

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

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

4 9 2
3 5 7
8 1 6

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

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

输入格式：

输入仅包含单组测试数据。
每组测试数据为一个3*3的矩阵，其中为0的部分表示被小明抹去的部分。
对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出格式：

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

样例输入

0 7 2
0 5 0
0 3 0

样例输出

6 7 2
1 5 9
8 3 4

---

思路分析

几种分析思路

暴力法

一般采用多重循环或全排列来进行暴力枚举， 但暴力枚举的前提一般是已给限定条件后才能执行。 对本题来说，限定条件多变，实现复杂，放弃。

搜索法

常规的搜索模板即可。

---

代码展示

#include<bits/stdc++.h> using namespace std;int a[15] = {0,1,2,3,4,5,6,7,8,9}; int b[15]; //保存最终答案 int vis[15];int num = 0; //num为边界条件 int sum = 0; //记录满足条件的矩阵个数void dfs(int step) {if(step == 9) { //连等只能用于赋值， 至于为什么，仔细想想原理 if( (a[3]+a[1]+a[2])==15 && (a[6]+a[4]+a[5])==15 && (a[9]+a[7]+a[8])==15 && (a[9]+a[3]+a[6])==15 && (a[2]+a[5]+a[8])==15 && (a[1]+a[4]+a[7])==15 && (a[1]+a[5]+a[9])==15 && (a[3]+a[5]+a[7])==15 ) {sum++;for(int i = 1; i <= 9; i++) b[i] = a[i];}}else for(int j = 1; j <= 9; j++) if(a[j] == 0) {for(int i = 1; i <= 9; i++) if(!vis[i]) {vis[i] = 1;a[j] = i;dfs(step+1);vis[i] = 0;a[j] = 0;}return;} } int main() {for(int i = 1; i <= 9; i++) {int x; cin>>x;if(x != 0) { vis[x] = 1; a[i]=x; num++;} }dfs(num);if(sum == 1) for(int i = 1; i <= 9; i++) {cout << b[i] << ' ';if(i==3 || i==6 || i==9) cout << '\n';}else cout << "Too many" << '\n'; return 0; }

---

感想与总结

1、蓝桥杯的绝大多数题都是搜索或暴力，而近两年纯暴力的题越来越少，取而代之的是模拟+搜索或暴力+搜索。

2、本题就是一道非常标准的 模拟+搜索 类型题。 关于暴力+搜索，可参考2016年B组7题的剪邮票， 也很经典， 题目+题解，传送门

3、对于对称类型的题， 一定要考虑是否有重复的情况出现。

---

把手举过头顶，突然张开五指，那么，恭喜你给自己放了个烟花！

总结

以上是生活随笔为你收集整理的【解题报告+通法】_九宫幻方 蓝桥杯 2017年C组第八题（dfs解法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。