13年 第四届 蓝桥杯C语言C组 第4题 幻方填空

标题: 幻方填空

    幻方是把一些数字填写在方阵中，使得行、列、两条对角线的数字之和都相等。

    欧洲最著名的幻方是德国数学家、画家迪勒创作的版画《忧郁》中给出的一个4阶幻方。

    他把1,2,3,...16 这16个数字填写在4 x 4的方格中。

    如图p1.jpg所示，即：

16 ?  ?  13

?  ?  11 ?

9  ?  ?  *

?  15 ?  1

    表中有些数字已经显露出来，还有些用?和*代替。

    请你计算出? 和 * 所代表的数字。并把 * 所代表的数字作为本题答案提交。

答案是一个整数，请通过浏览器直接提交该数字。

注意：不要提交解答过程，或其它辅助说明类的内容。

思路：接着振兴中华的思路，从(0,0)的位置开始走，走到（3,3）是结束。在走的过程中不是统计，从起点走到终点有多少种走法。而是判断这个非数值的位置上（？ *），放非图片中出现的数字，能不能满足题意。即每行每列每条对角线上的值都相等。

          当dfs从（0,0）走到（3,3），过程中不在图片的中存在的1----16的数字已经填了上去，走到结尾的时候，就要测试是否满足题意，满足就输出。

          dfs是一个试探的过程，这个方法行不行，不行就再换一种方法，直到当某一种解法存在且满足题意的时候，程序的使命，也就完成了。

过程：起始位置到终点dfs-->过程中在非数字位置上放数字-->放的这些数字是不重复的且满足在1--16中且不是图片上出现的数字-->走到结尾的时候检查放的这些数字是否满足题意-->满足题意就输出-->程序结束。

#include <stdio.h>
#include <stdlib.h>
int a[4][4]= {16,0,0,13,0,0,11,0,9,0,0,0,0,15,0,1};    //如图所示幻方数据 
int b[10]= {2,3,4,5,6,7,8,10,12,14};    //图片中没有的数字。 
int c[10]= {0};    //做标记，这个数用了就在对应的位置上标记为1。 
int ce() {    //检查每行每列每条对角线的值是否相同。 
	int i,j;
	int sum1=0,sum2=0;
	for(i=0; i<4; i++) {
		for(j=0; j<4; j++) {
			sum1+=a[i][j];
			sum2+=a[j][i];
		}
		if(sum1!=34||sum2!=34) {
			return 0;
		}
		sum1=0;
		sum2=0;
	}
	for(i=0; i<4; i++) {
		sum1+=a[i][i];
	}
	for(i=0,j=3; i<4&&j>=0; i++,j--) {
		sum2+=a[i][j];
	}
	if(sum1!=34||sum2!=34) {
		return 0;
	}
	return 1;


}
void print() {    //输出函数。 
	int i,j;
	for(i=0; i<4; i++) {
		for(j=0; j<4; j++) {
			printf("%3d ",a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
void dfs(int x,int y) {
	int i;
	if(x==4) {    //结尾，因为搜索的过程是从左到右，再到下一行，是通过一个小技巧完成的。当x=3的时候是第四行，第四行搜索完成到了第五行（x=4）就结束，前四行都走完了。走到头了。 
		if(ce()) {
			print();
			exit(0);
		}
		return ;
	}
	if(a[x][y]==0) {    //将问号 星号 设置为0 便于搜索  是零就是说应该填数的。 
		for(i=0; i<10; i++) {    //将b数组中i位置上的数，放在a[x][y]内，循环进行十次， a[x][y]==0这个位置上放十个数都放一边，所有的 a[x][y]==0都将b数组里面的数放过来一遍  历遍。 
			if(x==1&&a[0][0]+a[0][1]+a[0][2]+a[0][3]!=34)	return ;    //当x=1的时候，第一行已经都有数字了，判断这些数字是否等于三十四，从1加到16除以4等于34，不等于三十四就结束这个可能，因为这个可能肯定不满足题意。 
			if(x==2&&a[1][0]+a[1][1]+a[1][2]+a[1][3]!=34)	return ;
			if(x==3&&a[2][0]+a[2][1]+a[2][2]+a[2][3]!=34)	return ;
			if(!c[i]) {    //选中b[i]这个位置，之后c[i]=1就是表明这个位置的数字已经使用过了，不能再用。 
				c[i]=1;     
				a[x][y]=b[i];    //把b[i]的上的数字放在这个a[x][y]上。 
				dfs(x+(y+1)/4,(y+1)%4);    //小技巧，举几个示例  (3,2)  (2,2)  套这个公式，推推是等价的。 
				c[i]=0;			//这个可能已经尝试过了，进行下一种可能，在进行在一种可能的时候，要把数据还原到未使用之前。 
				a[x][y]=0;
			}
		}
	}
	else
	{
		dfs(x+(y+1)/4,(y+1)%4);    //图片上有数字，直接走过去。 
	}
}
int main() {
	dfs(0,0);    //深度优先搜索，起始位置。 
	return 0;
}