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

第8話 最後の改良の解説

コード主要部分再掲
   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==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;
   }

   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);
}

第6話までの改良と違う点は、

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

における

99

の存在です。
これは最終セルです。
言い換えると入れ子式人形の一番内側の人形です。
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);
     }

正確に言うと、
結果表示関数
void h(int **x,int n){
   for(char i=0;i<n;i++){
     for(char j=0;j<n;j++){
        if(n==3)cout<<x[i][j]<<" ";
        if(n>3)if(x[i][j]<10)cout<<"0"<<x[i][j]<<" "; else cout<<x[i][j]<<" ";
     }
     cout<<endl;
   }
   cout<<endl;
}
に、コンソールへの魔方陣の出力を依頼して、
今出来た魔方陣をカウントするという任務です。
それが、else文
     else{
        h(x,n);
        cn++;
        if(cn==100)return(cn);
     }

によって実行されています。
第6話までのプログラムでは、この仕事は
   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==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;
   }

試行錯誤を担当するfor文の中で行われていました。
ですが、そのミッションが

   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==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;
   }
に移動しましたので、for文ではその業務を遂行する必要がなくなり、
   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;
   }
とかなりスリムな形になったわけです。


さて、最終課題です。
乱数最適実験によって、
それぞれの次数に最適なシード値を見つけて、
乱数を組み込んで、
最低でも6次魔方陣までは、
20秒以内で100個生産できるように、
ソフトを改良して下さい。


第7話へ 第9話へ

a

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

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