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

第7話 n-1行目の改良

n-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[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-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[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(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 && s<n-1 && t==n-1){
     w=0;
     for(i=0;i<n-1;i++)w+=x[s][i];
     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-1 && t>0 && t<n-1){
     w=0;
     for(i=0;i<n-1;i++)w+=x[i][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;
     if(g+1<n*n){
        cn=f(k,x,n,cn,g+1,p,q);
     }
     else{
        h(x,n);
        cn++;
        if(cn==100)return(cn);
     }
     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;
     cn=f(x,n,cn,g+1);

     if(cn==100)return(cn);
     tobi:;
     if(v==1)k[i-1]=0;
   }
   return(cn);
}
参考ファイル

今回の改良は今までとは違います。
解説は次話で行うことにします。

改良前
w
対角線改良後
j

逆対角線改良後
r
1行目と1列目の改良後
g
n-1列目の改良
q
n-1行目の改良


乱数を入れなくても、6.4倍です。
ちょっとした工夫で速くなることが分かります。
さらに、乱数最適実験をして乱数を入れるともっと速くなります。


第6話へ 第8話へ

a

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

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