第20講 魔方陣汎用的生成プログラムVer.3=末項確定法
第5話 Ver.3(末項確定法)コード解説その2

解説続き
では
    if(y[g]==n-1 && x[g]==n-1){
      int i,w=0;
      for(i=0;i<n-1;i++)w+=m[i][i];
      int sa;
      sa=n*(n*n+1)/2-w;
      if(sa<=0 || sa>n*n)return;
      for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
      m[y[g]][x[g]]=sa;
      f(g+1);
      if(cn>9)return;
      return;
    }

においては何をしているのでしょうか。
      int i,w=0;
      for(i=0;i<n-1;i++)w+=m[i][i];

では、

0 1 2 3 4 5 6 7 8 9
0
1
2
3
4
5
6
7
8
9





ピンク色直前までの対角線の合計を計算しています。
そして、
      int sa;
      sa=n*(n*n+1)/2-w;

では魔方陣の行・列・対角線の合計との差を取っています。
もし、6次魔方陣であるなら
n*(n*n+1)/2=6*(6*6+1)/2=111
との差です。
      if(sa<=0 || sa>n*n)return;
そして、その差が0以下であったりn*n(6次の場合は36)を超えていたら、ひとつ手前のセル

0 1 2 3 4 5 6 7 8 9
0
1
2
3
4
5
6
7
8
9



に戻るように命令しています。


のセルに入れることのできる数字は
1から36までの数字ですから、
差が0以下または36より大きいなら、
ピンク
のセルに何を入れても、
合計をn*(n*n+1)/2にすることは不可能ですから、
より前の世界(入れ子式人形の外側の人形)に戻ってやり直すしかないわけです。

さて、
      for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
の働きは何でしょうか。たとえば、

12
29
39
47
63
72
86
93

の場合差は60です。しかし、

のセルに60を入れてしまうと、
数字が重複してはならないという魔方陣の基本のルールに反してしまいます。
するとこの場合にもひとつ手前の世界


に戻りやり直すしかないので、return;命令が遂行されます。

両検査
      if(sa<=0 || sa>n*n)return;
      for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;

に合格してはじめて

のセルに数字を入れることができます。
例えば

12
29
39
47
63
72
86
93

であれば7+12+29+39+47+63+72+86+93=448
で10次魔方陣の行・列・対角線の合計505との差は57で、重複がなく

12
29
39
47
63
72
86
93
57

対角線の合計も7+12+29+39+47+63+72+86+93+57=505
と条件を満たしています。それで、
      f(g+1);
によって、晴れて

0 1 2 3 4 5 6 7 8 9
0
1
2
3
4
5
6
7
8
9




の世界へと突き進むことができるのです。

















結局
    if(y[g]==n-1 && x[g]==n-1){
      int i,w=0;
      for(i=0;i<n-1;i++)w+=m[i][i];
      int sa;
      sa=n*(n*n+1)/2-w;
      if(sa<=0 || sa>n*n)return;
      for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
      m[y[g]][x[g]]=sa;
      f(g+1);
      if(cn>9)return;
      return;
    }

の役割は、条件を満たさなければ前の世界に強制帰還させ、
条件を満たせば、次の世界へと跳躍させることにあるのです。
したがいまして、
    int i,j,h,ii,iii;
    ii=0;
    if(n!=3 && n!=4){
      Random r = new Random(s);
      ii=(int)(r.nextInt(n*n));
    }
    for(i=1;i<n*n+1;i++){
      h=1;
      iii=(t*i+ii)%(n*n)+1;
      m[y[g]][x[g]]=iii;
      for(j=0;j<g;j++){
        if(m[y[g]][x[g]]==m[y[j]][x[j]]){
          h=0;
        }
      }
      if(h==1)f(g+1);
      if(cn>9)return;
      ow = System.currentTimeMillis();
      if((ow-hj)/1000>mn)return;
    }
の部分には一切触れさせないのです。

要するに


のセルにおいて無意味なループ処理を行わないことによって、
スピードアップが図られているのです。





第4話へ 第6話へ

戻る

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

初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第1部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第2部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第3部