蓝桥杯 九宫幻方

标题：九宫幻方     小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将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 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗  < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 注意： main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include <xxx> 不能通过工程设置而省略常用头文件。 提交程序时，注意选择所期望的语言类型和编译器类型。 -------------- 笨笨有话说：     我最喜欢这类题目了。既然九宫幻方一共也没有多少，我就不辞辛劳地一个一个写出来好了。

也不能太过分，好歹用个数组。    

思路：定义三个数组，a数组用于保存输入的九宫方格数。tep1用于填数，看是否满足要求，满足tot加1。tep2保存满足要求九宫方格数，当tot为1时输出。

#include <stdio.h> #include <string.h> #include<algorithm> using namespace std; int a[3][3]; int tep1[3][3]; int tep2[3][3]; int visied[10]={0};//标记被使用的数，值为1 int b[9];//将要填入的数 int f(){ //判断数组 行列 对角线 是否相等 相等返回1，不想等返回 0 int sum[10]; sum[0]=tep1[0][0]+tep1[0][1]+tep1[0][2]; sum[1]=tep1[1][0]+tep1[1][1]+tep1[1][2]; sum[2]=tep1[2][0]+tep1[2][1]+tep1[2][2]; sum[3]=tep1[0][0]+tep1[1][0]+tep1[2][0]; sum[4]=tep1[0][1]+tep1[1][1]+tep1[2][1]; sum[5]=tep1[0][2]+tep1[1][2]+tep1[2][2]; sum[6]=tep1[0][0]+tep1[1][1]+tep1[2][2]; sum[7]=tep1[0][2]+tep1[1][1]+tep1[2][0]; for(int i=1;i<8;i++){ if(sum[0]!=sum[i]) return 0; //不相等 } return 1; //相等 } int main() { int i, j, n,tot=0; memset(visied,0,sizeof(visied)); //数组重置0 for(i=0;i<3;i++){ for(j=0;j<3;j++){ scanf("%d",&a[i][j]); if(a[i][j]!=0) visied[a[i][j]]=1;//记录a数组的数被使用 } } for(i=0;i<3;i++){ //把数组a赋值给数组tep1 for(j=0;j<3;j++){ tep1[i][j]=a[i][j]; } } int bt=0; for(i=1;i<10;i++){ //1-9中数组a未使用的数赋值给b数组，用于填为0的地方 if(visied[i]!=1) b[bt++]=i; } do{ bt=0; for(i=0;i<3;i++){ //逐一填数 for(j=0;j<3;j++){ if(tep1[i][j]==0) tep1[i][j]=b[bt++]; } } if(f()){ //为真说明填入的数，数组满足三阶幻方要求 tot++; //统计变量，初始值为0，加1 for(i=0;i<3;i++){ //赋值给tpe2，保存满足要求的数组 for(j=0;j<3;j++){ tep2[i][j]=tep1[i][j]; } } for(i=0;i<3;i++){ //将初始数组a赋值给tpe1数组 for(j=0;j<3;j++){ tep1[i][j]=a[i][j]; } } } for(i=0;i<3;i++){ //不满足，将初始数组a赋值给tpe1数组 ，继续开始填数 for(j=0;j<3;j++){ tep1[i][j]=a[i][j]; } } }while(next_permutation(b,b+bt));//全排列 if(tot==1){ //只有一种满足要求的情况，输出 for(i=0;i<3;i++){ for(j=0;j<3;j++){ printf("%d\t",tep2[i][j]); } puts(""); } } if(tot>1) //多个情况 printf("Too Many"); return 0; }