第20講 一般種法による魔方陣ソフトの高速化
第1話 一般種とは?

特殊種法の工夫により、5次魔方陣の作成速度は改良版に比べて1822倍にもなりました。
計測していませんが、7次以降では軽く10万倍(一番最初のソフトと比べれば100億倍)を超えると思われますが、
それでも7次以降では歯が立ちませんでした。
さらに、特殊種法では3次と6次はできません。
そこで、さらに改良したいと思います。
それは一般種法による改良です。
前回の特殊種を、一辺種に変更します。
するとかなり高速化されると同時に、3次と6次もできるようになります。
というより理論的にはあらゆる魔方陣(2次の魔方陣は存在しませんので3次以上)を作成できます。
とっても現実的には、この方法をもってしても10次あたりが限界です。
10次あたりでも1個作成させるのに10分程度は時間が必要です。
11次あたりでは1時間以上必要でしょう。

では、一般種とは何でしょうか。一般種の例を挙げると、

0 4 2 0 4
0 3 3 1 3
4 0 2 3 1
4 1 0 4 1
2 2 3 2 1



3 3 0 2 2
0 2 4 3 1
0 1 2 3 4
4 0 4 1 1
3 4 0 1 2


















などです。
いずれの対角線、列、行の合計も10になっていて、そこは特殊種と同じですが、
特殊種との違いは一目瞭然です。
特殊種の場合は対角線上にも列にも行にも同じ数字が重複してはいけませんでしたが、
上の例においては、行も列も対角線上も同じ数字が重複しています。
白以外の色がついている数字は重複の例です。
色以外にも多数重複していることを確認して下さい。
このように対角線、列、行の合計がすべて10になっていれば、
数字の重複は問題にしない種が、一般種です。
特殊種は一般種の特別の場合であることが分かります。
だから、特殊な種ということで特殊種と名付けているのです。
ならばプログラミングにおいても、
特別な種から出発しないで、一般種から出発した方がよいと思うかもしれません。
ですが、実は一般種を作らせる普遍的なプログラミングを考えることは、
特殊種の場合より遙かに複雑で大変なのです。
というのは効率的に、一般種を作らせるには番号付け

10 11
12 13
14 15



4
10 11
12 13 14
15 16 17 18
19 20 21
4 22 23 24






















を改良して

10 12
11 14
13 15



4
10 11
12 15 16
13 17 19 20
14 21 23
4 18 22 24





















はy、はxに、ピンクはiに対応)
としなければなりません。
4次と5次に限定するなら簡単です。
もちろん偶数の場合と奇数の場合では番号付けのルールが違いますから、
偶数用と奇数用の二つは用意しなければならないわけですが、
どんな偶数でもどんな奇数でも通用するプログラミングを用意しなければなりません。
講義が進めば100次魔方陣あたりも作成可能になるからです。
ところが、普遍的なプログラミングをすることは非常にやっかいなのです。

ソースでいえば、i1とi2を変更しなければならないです。
        void i1(char n){
          char i,j,m;
          m=n/2;
          for(i=0;i<n*n;i++){
            if(i<n){
              x[i]=i;
              y[i]=i;
            }
            else if(i<2*n-1){
              x[i]=2*n-i-1;
              y[i]=i-n;
              if(x[i]<=y[i]){
                x[i]--;
                y[i]++;
              }
            }
            else if(i<2*n+(n*n-3*n)/2){
              x[i]=(i-2*n+1)%(n-2);
              y[i]=(i-2*n+1)/(n-2);
              if(x[i]>=y[i])x[i]++;
              if(x[i]>=n-y[i]-1)x[i]++;
            }
            else if(i<3*n-1+(n*n-3*n)/2){
              x[i]=i-2*n-(n*n-3*n)/2;
              y[i]=m;
              if(x[i]>=y[i])x[i]++;
            }
            else{
              x[i]=(i-2*n)%(n-2);
              y[i]=(i-2*n)/(n-2);
              if(x[i]>=n-y[i]-1)x[i]++;
              if(x[i]>=y[i])x[i]++;
            }
          }
        }
        void i2(char n){
          char i,m;
          m=n/2;
          for(i=0;i<n*n;i++){
            if(i<n){
              x[i]=i;
              y[i]=i;
            }
            else if(i<2*n){
              x[i]=2*n-i-1;
              y[i]=i-n;
            }
            else if(i<(m+1)*n){
              x[i]=(i-2*n)%(n-2);
              y[i]=(i-2*n)/(n-2);
              if(x[i]>=y[i])x[i]++;
              if(x[i]>=n-y[i]-1)x[i]++;
            }
            else{
              x[i]=(i-2*n)%(n-2);
              y[i]=(i-2*n)/(n-2);
              if(x[i]>=n-y[i]-1)x[i]++;
              if(x[i]>=y[i])x[i]++;
            }
          }
        }


比較的簡単な偶数版に限定してもかなり、難しいことを確認しておきましょう。

10 12
11 14
13 15


4 5
12 13 14 15
16 20 21 22
17 23 26 27
3 18 24 30 31
4 19 10 28 32 34
5 11 25 29 33 35

























はy、はx、ピンクはiに対応)
i<2*nの場合は、前の番号付けと同じですので、
i≧2*nに限定してみていきましょう。
iとyの対応を4次の場合で見ると、
y[8]=0,y[9]=0,y[10]=1,y[11]=2,y[12]=1,y[13]=3,y[14]=2,y[15]=2
つまり、数列0,0,1,2,1,3,2,2です。
このような数列の一般項は見つけられるのでしょうか。
しかも、nによらない普遍的(一般的)法則を見いださなければならないのです。
6次の場合は、
y[12]=0,y[13]=0,y[14]=0,y[15]=0,y[16]=1,y[17]=2,y[18]=3,y[19]=4,
y[20]=1,y[21]=1,y[22]=1,y[23]=2,y[24]=3,y[25]=5,y[26]=2,y[27]=2,
y[28]=4,y[29]=5,y[30]=3,y[31]=3,y[32]=4,y[33]=5,y[34]=4,y[35]=5
今回は数列0,0,0,0,1,2,3,4,1,1,1,2,3,5,2,2,4,5,3,3,4,5,4,5
こんな複雑な数列の一般項を求めることなどできるのでしょうか。
さらに10次の場合を見てみましょう。

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

ますます混迷を深めているように見ます。
こんな複雑な迷宮に出口などあるのでしょうか。






今回は、課題ということにはしません。
余りにも難しすぎるからです。
ですが、ファイトのある方は是非挑戦して下さい。
次話で、解答例を示しますが皆さんの方がもっとよいプログラミングをされているかもしれません。



第19講第8話へ 第20講(再講義)第2話へ


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