第16講 関数の再帰的呼び出しによる3次・4次魔方陣の作成
第2話 ソース例

皆さんどうでしたか。
かなりの難問でしょう。
私の予想では、ほとんどの方が苦戦して結局この第2話を開いてしまったのではないでしょうか。
もし、この第2話を開くことなくご自分でプログラミングできたとしたら、
あなたは初心者としては類い稀なる才能をおもちの方といってよいでしょう。
尚、いつも言っていることですが、これから示すものはあくまで解答例です。
もしかしたらもっとよいプログラミングを考えた方もいらっしゃるかもしれません。
実際に、この解答例はまだまだ改良の余地がありますので、
これから順を追って改良を加えていきます。
というのは、今回示す解答例は時間から考えれば4次魔方陣が限界です。
4次でさえ、20分も掛かってしまいます。

解答例
#pragma once
int n;
int a[10][10];
int s;
namespace 3次・4次の魔方陣作成 {
       ・
       ・
       ・

#pragma endregion
  private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
           n=int::Parse(textBox1->Text);
           s=0;
           f(0);
           int i;
           array<String^>^ x=gcnew array<String^>(16);
           x[9]=L"魔";x[10]=L"方";x[11]=L"陣";x[12]=L"総";x[13]=L"数";x[14]=L":";x[15]=s.ToString();
           for(i=0;i<9;i++)x[i]=L"";
           dataGridView1->Rows->Add(x);
        }
        void f(char g){
           int i,j,k,h,x,y,xx,yy,wa;
           array<String^>^ w=gcnew array<String^>(16);
           x=g%n;
           y=g/n;
           for(i=0;i<n*n;i++){
             a[y][x]=i+1;
             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 xx=j%n;
                 yy=j/n;
                 if(a[y][x]==a[yy][xx]){
                   h=0;
                   break;
                 }
               }
             }
             if(h==1){
               if(x==n-1){
                 wa=0;
                 for(j=0;j<n;j++)wa+=a[y][j];
                 if(wa!=n*(n*n+1)/2)h=0;
               }
             }
             if(h==1){
               if(y==n-1){
                 wa=0;
                 for(j=0;j<n;j++)wa+=a[j][x];
                 if(wa!=n*(n*n+1)/2)h=0;
               }
             }
             if(h==1){
               if(x==n-1 && y==n-1){
                 wa=0;
                 for(j=0;j<n;j++)wa+=a[j][j];
                 if(wa!=n*(n*n+1)/2)h=0;
               }
             }
             if(h==1){
               if(x==0 && y==n-1){
                 wa=0;
                 for(j=0;j<n;j++)wa+=a[n-j-1][j];
                 if(wa!=n*(n*n+1)/2)h=0;
               }
             }
             if(h==1){
               if(g<n*n-1){
                 f(g+1);
               }
               else{
                 for(j=0;j<n;j++){
                   for(k=0;k<n;k++){
                      w[k]=(a[j][k]).ToString();
                   }
                   dataGridView1->Rows->Add(w);
                   }
                   for(j=0;j<16;j++)w[j]=L"";
                   dataGridView1->Rows->Add(w);
                   s++;
                 }
               }
             }
          }
  };
}



(コピーペースト用

#pragma once
int n;
int a[10][10];
int s;
namespace 3次・4次の魔方陣作成 {
       ・
       ・
       ・
#pragma endregion
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
n=int::Parse(textBox1->Text);
s=0;
f(0);
int i;
array<String^>^ x=gcnew array<String^>(16);
x[9]=L"魔";x[10]=L"方";x[11]=L"陣";x[12]=L"総";x[13]=L"数";x[14]=L":";x[15]=s.ToString();
for(i=0;i<9;i++)x[i]=L"";
dataGridView1->Rows->Add(x);
}
void f(char g){
int i,j,k,h,x,y,xx,yy,wa;
array<String^>^ w=gcnew array<String^>(16);
x=g%n;
y=g/n;
for(i=0;i<n*n;i++){
a[y][x]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
xx=j%n;
yy=j/n;
if(a[y][x]==a[yy][xx]){
h=0;
break;
}
}
}
if(h==1){
if(x==n-1){
wa=0;
for(j=0;j<n;j++)wa+=a[y][j];
if(wa!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y==n-1){
wa=0;
for(j=0;j<n;j++)wa+=a[j][x];
if(wa!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(x==n-1 && y==n-1){
wa=0;
for(j=0;j<n;j++)wa+=a[j][j];
if(wa!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(x==0 && y==n-1){
wa=0;
for(j=0;j<n;j++)wa+=a[n-j-1][j];
if(wa!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(g<n*n-1){
f(g+1);
}
else{
for(j=0;j<n;j++){
for(k=0;k<n;k++){
w[k]=(a[j][k]).ToString();
}
dataGridView1->Rows->Add(w);
}
for(j=0;j<16;j++)w[j]=L"";
dataGridView1->Rows->Add(w);
s++;
}
}
}
}
};
}



相当難解なプログラムソースですので、2,3話かけて解説していきますが、
何故、このプログラミングだと4次魔方陣が限界なのかを説明しておきましょう。
このプログラミングは力業です。
すべての場合を調べて、条件に合うものを表示させるというプログラミングです。
3次魔方陣なら9個の順列と同じだけ場合の数があって、
9!=362880通りです。
4次魔方陣の場合は16個の順列と同じで、
16!すなわち約20900000000000通りあります。
20900000000000通り調べるのですからさすがのコンピュータも時間が掛かります。
環境にもよりますが、20分程度は掛かります。
尚、条件に合うものは3次方陣362880通りの場合の数に対して、8個
4次の場合は約20900000000000通りに対して7040個しかありません。
パーセントで言うと、3次の場合0.0022%、4次の場合0.0000000336%にすぎません。
もっとわかりやすく言うと、
3次では45360個の場合に対して1個、4次では約2971987200個の場合に対して1個しか魔方陣にならないです。
4次魔方陣はなんと約30億の順列中1個しか魔方陣にならないです。
如何に条件が厳しいか分かります。
5次ではもちろん天文学的数字になります。
実は、3次魔方陣の8個は対称移動や鏡像移動などをすれば合同です。
ですから3次魔方陣の場合は本質的には1個しか魔方陣はありません。
4次魔方陣の場合は、7040÷8=880個です。
5次では、合同を排除しても約2.7億個解答が存在することが40台のパソコンを並列に走らせて証明されています。
鏡像移動なども1個と数えれば約21億個も存在するのです。
6次以上では何個存在するのかは、まだ分かっていません。
スーパコンピュータを使ったとしても、6次魔方陣が何個存在すのかが分からないのです。
それは、兆や京(兆の1万倍)を遙かに超える単位であることは間違いありません。

しがたって、5次以上の魔方陣に対してはかなりの工夫を加えないと太刀打ちできません。
プログラミングにおいて大事なことはアイデアなのです。




第11講第6話へ
 第12講第1話へ 第14講第10話へ 第15講第10話へ 第16講第1話へ 第16講第3話へ



VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座