幻方填空

港控/mmm° 2022-08-02 12:40 153阅读 0赞

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

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

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

如图p1.jpg所示，即：

16?  ? 13

?  ?  11 ?

9  ? ?  \*

?  15 ?  1

![SouthEast][]

![Image 1][]

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

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

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

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

参考代码：

#include<stdio.h>
    	
    	int a[4][4]={
       {16,0,0,13},{0,0,11,0},{9,0,0,0},{0,15,0,1}};
    	int b[17]={0};
    	
    	int palce(int t){
    		int sum=0,temp,i,j;
    		if(t<8)
    			return 1;
    		else{
    			for(i=0;i<4;i++)
    				sum+=a[0][i];
    			for(i=0;i<(t+1)/4;i++){
    				temp=0;
    				for(j=0;j<4;j++){
    					temp+=a[i][j];
    				}
    				if(temp!=sum)
    					return 0;
    			}
    		}
    		return 1;
    	}
    	
    	
    	void backtrack(int t){
    		int i,j,x,y,sum=0,temp,flag=1;
    		if(t==16){
    			for(i=0;i<4;i++)
    				sum+=a[0][i];
    			for(i=0;i<4;i++){
    				temp=0;
    				for(j=0;j<4;j++)
    					temp+=a[j][i];
    				if(temp!=sum){
    					flag=0;
    					break;
    				}
    			}
    			temp=0;
    			for(i=0;i<4;i++)
    				temp+=a[i][i];
    			if(temp!=sum)
    				flag=0;
    			temp=0;
    			for(i=0;i<4;i++)
    				temp+=a[i][4-1-i];
    			if(temp!=sum)
    				flag=0;
    			if(flag){
    				for(i=0;i<4;i++){
    					for(j=0;j<4;j++)
    						printf("%d\t",a[i][j]);
    					putchar('\n');
    				}
    			}
    		}else{
    			x=t/4;
    			y=t%4;
    			if(a[x][y]!=0)
    				backtrack(t+1);
    			else{
    				for(i=1;i<17;i++){
    					if(!b[i]){
    						a[x][y]=i;
    						b[i]++;
    						if(palce(t))
    							backtrack(t+1);
    						b[i]--;
    						a[x][y]=0;
    					}
    				}
    			}
    		}
    	}
    	
    	int main(){
    		int i,j;
    		
    		for(i=0;i<4;i++)
    			for(j<10;j<4;j++)
    				b[a[i][j]]++;
    		
    		backtrack(0);
    		
    		return 0;
    	}

答案：12

运行结果：

![Image 1][] ![SouthEast 1][]

[SouthEast]: /images/20220731/183c689f6b5046f49ecace9e9accaaa7.png
[Image 1]: 
[SouthEast 1]: /images/20220731/4796fc71b58043f0a88b1d43a2d4b406.png