标题：四阶幻方把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时的所有方案数字，不要填写任何多余内容或说明文字。

 

记:

一开始直接用dfs搜索，发现时间太长，于是找规律

发现，幻方的值，为1累加到16的和除以阶数4

(所以类似的n阶幻方也可以这么做？)

另外一个3阶的题目用同样方法也行

 

从而添加剪枝操作后，运行时间约1min

 

示例代码:

1 #include 
     
       2 #define MAX 16    /*可放置的最大数*/  3 #define N 4        /*阶数*/ 4  5 int key = 34;    /*1到MAX的累加和除以MAX*/ 6 int count = 0;    /*满足条件的解*/ 7 int arr[N+1][N+1] = {
   0}; 8 int f[MAX+1] = {
   0}; 9 10 void dfs(int x)11 {12     int i,j,k,s;          /*s用于剪枝操作*/13     14     if (x > MAX)15     {            16         i = arr[1][1]+arr[2][2]+arr[3][3]+arr[4][4];17         j = arr[1][4]+arr[2][3]+arr[3][2]+arr[4][1];18         if (i != key || j != key)19         {20             return;21         }            22         for (i = 1 ; i <= N ; i ++)23         {24             s = 0;25             for (j = 1 ; j <= N ; j ++)26             {27                 s += arr[j][i];28             }29             if (s != key)30             {31                 return;32             }                33         }                34         35         count ++;36         return;37     }38     39     for (i = 2 ; i <= MAX ; i ++)/*遍历2-MAX*/40     {41         if (!f[i])42         {            43             for (j = 1 ; j <= N ; j ++)44             {45                 s = 0;46                 for (k = 1 ; k <= N ; k ++)47                 {48                     if (!arr[j][k])49                     {50                         f[i] = 1;51                         arr[j][k] = i;52                         break;53                     }54                     s += arr[j][k];55                 }56                 if (f[i])57                 {58                     break;59                 }60                 if (s != key)61                 {62                     return;63                 }                    64             }65             dfs(x+1);66             arr[j][k] = 0;67             f[i] = 0;68         }69     }        70     71     return ;72 }73 74 int main(void)75 {76     f[1] = 1;77     arr[1][1] = 1;78     dfs(2);79     printf("%d",count);/*416*/80     return 0;81 }