华师一附中OI组

标题: 偶数阶幻方 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-8-21 10:19
标题: 偶数阶幻方
本帖最后由 倚窗倾听风吹雨 于 2018-8-21 13:23 编辑
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<iomanip>
  4. using namespace std;
  5. int a[6][6];
  6. int ans;
  7. bool v[17];
  8. int main()
  9. {
  10.     freopen("偶数阶幻方.txt","w",stdout);
  11.     for(int i=1;i<=16;i++)
  12.     {
  13.         if(i==1)cout<<i<<"i"<<endl;
  14.         a[1][1]=i;v[i]=1;
  15.         for(int j=1;j<=16;j++)
  16.         {
  17.             if(v[j])continue;
  18.             if(i==1 && j==4)cout<<j<<"j"<<endl;
  19.             a[1][2]=j;v[j]=1;
  20.             for(int k=1;k<=16;k++)
  21.             {
  22.                 if(v[k])continue;
  23.                 a[1][3]=k;
  24.                 a[1][4]=34-i-j-k;
  25.                 v[k]=1;
  26.                 if(v[a[1][4]] || a[1][4]<=0 || a[1][4]>16)
  27.                 {
  28.                     v[k]=0;
  29.                     continue;
  30.                 }
  31.                 v[a[1][4]]=1;
  32.                 for(int l=1;l<=16;l++)
  33.                 {
  34.                     if(v[l])continue;
  35.                     a[2][1]=l;v[l]=1;
  36.                     a[2][2]=34-l-i-j;
  37.                     if(v[a[2][2]] || a[2][2]<=0 || a[2][2]>16)
  38.                     {
  39.                         v[l]=0;
  40.                         continue;
  41.                     }
  42.                     v[a[2][2]]=1;
  43.                     for(int q=1;q<=16;q++)
  44.                     {
  45.                         if(v[q])continue;
  46.                         a[2][3]=q;v[q]=1;
  47.                         a[2][4]=i+j-q;
  48.                         if(v[a[2][4]] || a[2][4]<=0 || a[2][4]>16)
  49.                         {
  50.                             v[q]=0;
  51.                             continue;
  52.                         }
  53.                         v[a[2][4]]=1;
  54.                         for(int w=1;w<=16;w++)
  55.                         {
  56.                             if(v[w])continue;
  57.                             a[3][1]=w;v[w]=1;
  58.                             a[4][1]=34-i-l-w;
  59.                             if(v[a[4][1]] || a[4][1]<=0 || a[4][1]>16)
  60.                             {
  61.                                 v[w]=0;
  62.                                 continue;
  63.                             }
  64.                             v[a[4][1]]=1;
  65.                             for(int e=1;e<=16;e++)
  66.                             {
  67.                                 if(v[e])continue;
  68.                                 a[3][2]=e;v[e]=1;
  69.                                if(i+j+k-q-e!=34-i-l-w)
  70.                                 {
  71.                                     v[e]=0;
  72.                                     continue;
  73.                                 }
  74.                                 a[3][3]=i+j+l-q-e;
  75.                                 if(v[a[3][3]] || a[3][3]<=0 || a[3][3]>16)
  76.                                 {
  77.                                     v[e]=0;
  78.                                     continue;
  79.                                 }
  80.                                 v[a[3][3]]=1;
  81.                                 a[3][4]=34-w-i-j-l+q;
  82.                                 if(v[a[3][4]] || a[3][4]<=0 || a[3][4]>16)
  83.                                 {
  84.                                     v[a[3][3]]=0;
  85.                                     v[e]=0;
  86.                                     continue;
  87.                                 }
  88.                                 v[a[3][4]]=1;
  89.                                 a[4][2]=i+l-e;
  90.                                 if(v[a[4][2]] || a[4][2]<=0 || a[4][2]>16)
  91.                                 {
  92.                                     v[a[3][3]]=0;
  93.                                     v[e]=0;
  94.                                     v[a[3][4]]=0;
  95.                                     continue;
  96.                                 }
  97.                                 v[a[4][2]]=1;
  98.                                 a[4][3]=34-k-i-j-l+e;
  99.                                 if(v[a[4][3]] || a[4][3]<=0 || a[4][3]>16)
  100.                                 {
  101.                                     v[a[3][3]]=0;
  102.                                     v[e]=0;
  103.                                     v[a[3][4]]=0;
  104.                                     v[a[4][2]]=0;
  105.                                     continue;
  106.                                 }
  107.                                 v[a[4][3]]=1;
  108.                                 a[4][4]=w-34+i+k+j+l;
  109.                                 if(v[a[4][4]] || a[4][4]<=0 || a[4][4]>16)
  110.                                 {
  111.                                     v[a[3][3]]=0;
  112.                                     v[e]=0;
  113.                                     v[a[3][4]]=0;
  114.                                     v[a[4][2]]=0;
  115.                                     v[a[4][3]]=0;
  116.                                     continue;
  117.                                 }
  118.                                 v[a[4][4]]=1;
  119.                                 for(int r=1;r<=4;r++)
  120.                                 {
  121.                                     for(int t=1;t<=4;t++)
  122.                                         cout<<setw(3)<<a[r][t];
  123.                                     cout<<endl;
  124.                                 }
  125.                                 ans++;
  126.                                 cout<<endl;
  127.                                 v[a[3][3]]=0;
  128.                                 v[e]=0;
  129.                                 v[a[3][4]]=0;
  130.                                 v[a[4][2]]=0;
  131.                                 v[a[4][3]]=0;
  132.                                 v[a[4][4]]=0;
  133.                             }
  134.                             v[w]=0;
  135.                             v[a[4][1]]=0;
  136.                         }
  137.                         v[q]=0;
  138.                         v[a[2][4]]=0;
  139.                     }
  140.                     v[l]=0;
  141.                     v[a[2][2]]=0;
  142.                 }
  143.                 v[k]=0;
  144.                 v[a[1][4]]=0;
  145.             }
  146.             v[j]=0;
  147.         }
  148.         v[i]=0;
  149.     }
  150.     cout<<ans<<endl;
  151.     return 0;
  152. }
复制代码

作者: 吴语林    时间: 2018-8-21 10:35
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <algorithm>
  7. #include <queue>
  8. #include <stack>
  9. using namespace std;
  10. int a[10][10],book[20],all=0;
  11. void dfs(int x,int y,int num)
  12. {
  13.         if(y==4)
  14.                 y=1,x++;
  15.         else
  16.                 y++;
  17.         if(x==1&&y==4)
  18.         {
  19.                 a[1][4]=34-a[1][1]-a[1][2]-a[1][3];
  20.                 if(a[1][4]<=0||a[x][y]>16||book[a[x][y]])
  21.                         return;
  22.                 book[a[x][y]]=1;
  23.                 dfs(x,y,a[x][y]);
  24.                 book[a[x][y]]=0;
  25.         }
  26.         else if(x==2&&y==2)
  27.         {
  28.                 a[2][2]=34-a[1][1]-a[1][2]-a[2][1];
  29.                 if(a[2][2]<=0||a[x][y]>16||book[a[x][y]])
  30.                         return;
  31.                 book[a[x][y]]=1;
  32.                 dfs(x,y,a[x][y]);
  33.                 book[a[x][y]]=0;
  34.         }
  35.         else if(x==2&&y==4)
  36.         {
  37.                 a[2][4]=34-a[2][1]-a[2][2]-a[2][3];
  38.                 if(a[2][4]<=0||a[x][y]>16||a[2][4]!=34-a[1][3]-a[1][4]-a[2][3]||book[a[x][y]])
  39.                         return;
  40.                 book[a[x][y]]=1;
  41.                 dfs(x,y,a[x][y]);
  42.                 book[a[x][y]]=0;
  43.         }
  44.         else if(x==3&&y==3)
  45.         {
  46.                 a[3][3]=34-a[3][2]-a[2][2]-a[2][3];
  47.                 if(a[3][3]<=0||a[x][y]>16||book[a[x][y]])
  48.                         return;
  49.                 book[a[x][y]]=1;
  50.                 dfs(x,y,a[x][y]);
  51.                 book[a[x][y]]=0;
  52.         }
  53.         else if(x==3&&y==4)
  54.         {
  55.                 a[3][4]=34-a[3][1]-a[3][2]-a[3][3];
  56.                 if(a[3][4]<=0||a[x][y]>16||book[a[x][y]])
  57.                         return;
  58.                 book[a[x][y]]=1;
  59.                 dfs(x,y,a[x][y]);
  60.                 book[a[x][y]]=0;
  61.         }
  62.         else if(x==4&&y==1)
  63.         {
  64.                 a[4][1]=34-a[1][1]-a[2][1]-a[3][1];
  65.                 if(a[4][1]<=0||a[x][y]>16||book[a[x][y]]||a[4][1]!=34-a[1][4]-a[2][3]-a[3][2])
  66.                         return;
  67.                 book[a[x][y]]=1;
  68.                 dfs(x,y,a[x][y]);
  69.                 book[a[x][y]]=0;
  70.         }
  71.         else if(x==4&&y==2)
  72.         {
  73.                 a[4][2]=34-a[1][2]-a[2][2]-a[3][2];
  74.                 if(a[4][2]<=0||a[x][y]>16||a[4][2]!=34-a[3][1]-a[3][2]-a[4][1]||book[a[x][y]])
  75.                         return;
  76.                 book[a[x][y]]=1;
  77.                 dfs(x,y,a[x][y]);
  78.                 book[a[x][y]]=0;
  79.         }
  80.         else if(x==4&&y==3)
  81.         {
  82.                 a[4][3]=34-a[1][3]-a[2][3]-a[3][3];
  83.                 if(a[4][3]<=0||a[x][y]>16||book[a[x][y]])
  84.                         return;
  85.                 book[a[x][y]]=1;
  86.                 dfs(x,y,a[x][y]);
  87.                 book[a[x][y]]=0;
  88.         }
  89.         else if(x==4&&y==4)
  90.         {
  91.                 a[4][4]=34-a[1][4]-a[2][4]-a[3][4];
  92.                 if(a[4][4]<=0||a[x][y]>16||book[a[x][y]]||a[4][4]!=34-a[3][3]-a[3][4]-a[4][3]||a[4][4]!=34-a[4][1]-a[4][2]-a[4][3]||a[4][4]!=34-a[1][1]-a[2][2]-a[3][3])
  93.                         return;
  94.                 for(int i=1;i<=4;i++)
  95.                 {
  96.                         for(int j=1;j<=4;j++)
  97.                                 printf("%2d ",a[i][j]);
  98.                         printf("\n");
  99.                 }
  100.                 printf("\n---------------\n");
  101.                 all++;
  102.         }
  103.         else
  104.         {
  105.                 for(int i=1;i<=16;i++)
  106.                         if(!book[i])
  107.                         {
  108.                                 book[i]=1;
  109.                                 a[x][y]=i;
  110.                                 dfs(x,y,i);
  111.                                 book[i]=0;
  112.                         }
  113.         }
  114. }
  115. int main()
  116. {
  117.         freopen("11.txt","w",stdout);
  118.         for(int i=1;i<=16;i++)
  119.         {
  120.                 book[i]=1;
  121.                 a[1][1]=i;
  122.                 dfs(1,1,i);
  123.                 book[i]=0;
  124.         }
  125.         printf("\n%d",all);
  126.     return 0;
  127. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-8-21 11:01
本帖最后由 倚窗倾听风吹雨 于 2018-8-21 13:24 编辑

以下是检验程序
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int wrong,r,a[5][5],sum;
  5. bool v[17],flag;
  6. int main()
  7. {
  8.     freopen("偶数阶幻方.txt","r",stdin);
  9.     cin>>n;///输入总结果数
  10.     while(n--)
  11.     {
  12.         flag=0;
  13.         for(int i=1;i<=4;i++)
  14.             for(int j=1;j<=4;j++)
  15.             {
  16.                 cin>>a[i][j];
  17.                 v[a[i][j]]=1;
  18.             }
  19.         for(int i=1;i<=16;i++)
  20.             if(!v[i])
  21.             {
  22.                 wrong++;
  23.                 flag=1;
  24.                 break;
  25.             }
  26.         if(flag==1)continue;
  27.         for(int i=1;i<=4;i++)
  28.         {
  29.             sum=0;
  30.             for(int j=1;j<=4;j++)
  31.             sum+=a[i][j];
  32.             if(sum!=34)
  33.             {
  34.                 wrong++;
  35.                 flag=1;
  36.                 break;
  37.             }
  38.         }
  39.         if(flag==1)continue;
  40.         for(int j=1;j<=4;j++)
  41.         {
  42.             sum=0;
  43.             for(int i=1;i<=4;i++)
  44.             sum+=a[i][j];
  45.             if(sum!=34)
  46.             {
  47.                 wrong++;
  48.                 flag=1;
  49.                 break;
  50.             }
  51.         }
  52.         if(flag==1)continue;
  53.         sum=a[1][1]+a[1][2]+a[2][1]+a[2][2];
  54.         if(sum!=34)
  55.         {
  56.             wrong++;
  57.             continue;
  58.         }
  59.         sum=a[1][3]+a[1][4]+a[2][3]+a[2][4];
  60.         if(sum!=34)
  61.         {
  62.             wrong++;
  63.             continue;
  64.         }
  65.         sum=a[2][2]+a[2][3]+a[3][2]+a[3][3];
  66.         if(sum!=34)
  67.         {
  68.             wrong++;
  69.             continue;
  70.         }
  71.         sum=a[3][1]+a[3][2]+a[4][1]+a[4][2];
  72.         if(sum!=34)
  73.         {
  74.             wrong++;
  75.             continue;
  76.         }
  77.         sum=a[3][3]+a[3][4]+a[4][3]+a[4][4];
  78.         if(sum!=34)
  79.         {
  80.             wrong++;
  81.             continue;
  82.         }
  83.         sum=0;
  84.         for(int i=1;i<=4;i++)
  85.         sum+=a[i][i];
  86.         if(sum!=34)
  87.         {
  88.             wrong++;
  89.             continue;
  90.         }
  91.         sum=0;
  92.         sum=a[1][4]+a[2][3]+a[3][2]+a[4][1];
  93.         if(sum!=34)
  94.         {
  95.             wrong++;
  96.             continue;
  97.         }
  98.         r++;
  99.     }
  100.     cout<<r<<" "<<wrong<<endl;
  101.     return 0;
  102. }
复制代码
输出的结果；

作者: admin    时间: 2018-8-22 19:40
很好！还有检验程序，但是为什么感觉程序都是如此的复杂呢？



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2