第20講 末項確定法による魔方陣自動生成ソフトの高速化

第5話 1行目と1列目の改良

1行目と1列目の改良プログラム例
long f(int *k,int **x,int n,long cn,int g,int *p,int *q){
   int i,j,s,t,w,v;
   s=q[g];
   t=p[g];
   if(s==n-1 && t==n-1){
     w=0;
     for(i=0;i<n-1;i++)w+=x[i][i];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[n-1][n-1]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }
   if(s==n-1 && t==0){
     w=0;
     for(i=0;i<n-1;i++)w+=x[i][n-1-i];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[n-1][0]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }
  if(s==0 && t==n-2){
     w=0;
     for(i=0;i<n-2;i++)w+=x[s][i];
     w+=x[s][n-1];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[s][t]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }
   if(s==n-2 && t==0){
     w=0;
     for(i=0;i<n-2;i++)w+=x[i][t];
     w+=x[n-1][t];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[s][t]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }

   for(i=1;i<n*n+1;i++){

     x[s][t]=i;
     v=0;
     if(k[i-1]==0){
        k[i-1]=1;
        v=1;
     }
     else{
        goto tobi;
     }
     if(s>0 && s<n-1 && t==n-1){
        w=0;
        for(j=0;j<n;j++)w+=x[s][j];
        if(w!=n*(n*n+1)/2)goto tobi;
     }
     if(s==n-1 && t>0 && t<n-1){
        w=0;
        for(j=0;j<n;j++)w+=x[j][t];
        if(w!=n*(n*n+1)/2)goto tobi;
     }
     if(g+1<n*n){
        cn=f(x,n,cn,g+1);
        if(cn==100)return(cn);
     }
     else{
        h(x,n);
        cn++;
        if(cn==100)return(cn);
     }
     tobi:;
     if(cn==100)return(cn);
     if(v==1)k[i-1]=0;
   }
   return(cn);
}
参考ファイル

今回の改良も
  if(s==0 && t==n-2){
     w=0;
     for(i=0;i<n-2;i++)w+=x[s][i];
     w+=x[s][n-1];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[s][t]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }
   if(s==n-2 && t==0){
     w=0;
     for(i=0;i<n-2;i++)w+=x[i][t];
     w+=x[n-1][t];
     w=n*(n*n+1)/2-w;
     if(w<1 || w>n*n)return(cn);
     if(k[w-1]==1)return(cn);
     x[s][t]=w;
     k[w-1]=1;
     cn=f(k,x,n,cn,g+1,p,q);
     k[w-1]=0;
     return(cn);
   }

を付け加えたことと
     if(s==0 && t==n-2){
        w=0;
        for(j=0;j<n;j++)w+=x[s][j];
        if(w!=n*(n*n+1)/2)goto tobi;
     }
     for(j=0;j<n;j++)w+=x[j][t];
        if(w!=n*(n*n+1)/2)goto tobi;
     }

を削ったことです。


改良前
w
対角線改良後
j

逆対角線改良後
r
1行目と1列目の改良後
g
今まで一番効果がありましたが、
次の改良は、より劇的です。

0 1 2 3 4 5 6 7 8 9
0 0 20 21 22 23 24 25 26 27 10
1 28 1 36 37 38 39 40 41 11 42
2 29 43 2 50 51 52 53 12 54 55
3 30 44 56 3 62 63 13 64 65 66
4 31 45 57 67 4 14 72 73 74 75
5 32 46 58 68 15 5 80 81 82 83
6 33 47 59 16 76 84 6 88 89 90
7 34 48 17 69 77 85 91 7 94 95
8 35 18 60 70 78 86 92 96 8 98
9 19 49 61 71 79 87 93 97 99 9

42
55
66
75
83
90
95
98

の部分の改良です。



第4話へ 第6話へ

a

eclipse c++ 入門講義第1部へ

魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ