题目描述
把1~16的数字填入4x4的方格中，使得行、列以及两个对角线的和都相等，满足这样的特征时称为：四阶幻方。
四阶幻方可能有很多方案。如果固定左上角为1，请计算一共有多少种方案。
比如：
1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9
以及：
1 12 13 8
2 14 7 11
15 3 10 6
16 5 4 9
就可以算为两种不同的方案。
输出
请提交左上角固定为1时的所有方案数字
题意：就是左上角固定填好1，其他位置填数，每个数只能填一次，然后每行，每列，两条对角线的和都相等就算符合条件，求出一共有多少种符合条件的方案
思路：DFS再剪枝下，这题是填空题，最后直接输出即可
代码：
#pragma GCC optimize(2) #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<map> #include<stack> #include<set> #include<vector> #include<queue> #include<iomanip> using namespace std; int a[5][5]; int book[17]; int sum=34; int ans=0; bool jd(int i) // 检查行 { int num=0; for(int j=0;j<4;j++) num+=a[i][j]; if(num!=sum) return false; return true; } bool check() // 核对是否满足要求 { int num1=a[0][0]+a[1][1]+a[2][2]+a[3][3];// 主对角线 if(num1!=sum) return false; int num2=a[0][3]+a[1][2]+a[2][1]+a[3][0]; //副对角线 if(num2!=sum) return false; for(int i=0;i<4;i++) //行 { if(!jd(i)) return false; } for(int j=0;j<4;j++) // 列 { int k=a[0][j]+a[1][j]+a[2][j]+a[3][j]; if(k!=sum) return false; } return true; } void dfs(int n) { if(n==16) { if(check()) ans++; return ; } if(n%4==0) // 剪枝下 { if(!jd(n/4-1)) return ; } for(int i=2;i<17;i++) //填充 { if(!book[i]) { book[i]=1; a[n/4][n%4]=i; dfs(n+1); book[i]=0; } } } int main() { a[0][0]=1; dfs(1); cout<<ans<<endl; //cout<<416<<endl; //最后直接输出即可 return 0; }
