四阶幻方

爱被打了一巴掌 2022-05-28 01:47 201阅读 0赞

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

耗时20s才出结果的

#include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    int ans,sum;
    int a[5][5];
    int vis[17];
    void dfs(int step)
    {
    
        int x=step/4;
        int y=step%4;
    
        if(step>=16)
        {
            ans++;
            int s=0,ok=0;
            for(int i=0; i<4; i++)
            {
                s=0;
                for(int j=0; j<4; j++)
                    s=s+a[j][i];
                if(s!=34)
                {
                    ok=1;
                    return ;
                }
            }
            s=a[3][0]+a[3][1]+a[3][2]+a[3][3];
            if(s!=34)
                return ;
            s=a[0][0]+a[1][1]+a[2][2]+a[3][3];
            if(s!=34)
               return ;
            s=a[3][0]+a[2][1]+a[1][2]+a[0][3];
            if(s!=34)
                return ;
            if(!ok)
            {
                sum++;
    //            for(int i=0; i<4; i++)
    //            {
    //                for(int j=0; j<4; j++)
    //                {
    //                    printf("%d ",a[i][j]);
    //                }
    //                printf("\n");
    //            }
    //            printf("\n");
            }
            return ;
        }
        else if(step==4)
        {
            if(a[0][0]+a[0][1]+a[0][2]+a[0][3]!=34)
                return ;
        }
        else if(step==8)
        {
            if(a[1][0]+a[1][1]+a[1][2]+a[1][3]!=34)
                return ;
        }
        else if(step==12)
        {
            if(a[2][0]+a[2][1]+a[2][2]+a[2][3]!=34)
                return ;
        }
        for(int i=2; i<=16; i++)
        {
            if(!vis[i])
            {
                a[x][y]=i;
                vis[i]=1;
                dfs(step+1);
                vis[i]=0;
            }
        }
    }
    int main()
    {
        sum=0;
        a[0][0]=1;
        dfs(1);
        printf("%d\n",sum);
        return 0;
    }