第10講 関数の再帰的使用による魔方陣の自動生成
第5話 n次魔方陣自動生成ソフト
n次魔方陣生成ソフトコード例
#include<stdio.h>
void f(int g);
int x[25];
int n, cn;
int main() {
  printf("これはすべてのn次魔方陣を求めるソフトです。\n");
  printf("何次の魔方陣を発生させるのかをnに入力し\n");
  printf("エンターするとn次魔方陣がすべて生成されます。\n");
  printf("n=");
  scanf("%d", &n);
  cn = 0;
  f(0);
  printf("生成された%d次魔方陣は%d個です。\n", n,cn);
  return(0);
}
void f(int g) {
  int i, j,k, h,hh,w;
  for (i = 0; i<n*n; i++) {
    if (g == 0)x[g] = i + 1;
    h = 1;
    if (g>0) {
      for (j = 0; j<g; j++) {
        if (x[j] == i + 1) {
          h = 0;
          break;
        }
      }
      if (h == 1)x[g] = i + 1;
    }
    if (h == 1) {
      if (g + 1 < n*n) {
        f(g + 1);
      }
      else {
        hh=1;
        for (j = 0; j < n; j++) {
          w=0;
          for (k = 0; k < n; k++) {
            w+=x[n*j+k];
          }
          if(w!=n*(n*n+1)/2){
            hh=0;
            break;
          }
        }
        if(hh==1){
          for (j = 0; j < n; j++) {
            w=0;
            for (k = 0; k < n; k++) {
              w+=x[n*k+j];
            }
            if(w!=n*(n*n+1)/2){
              hh=0;
              break;
            }
          }
        }
        
if(hh==1){
          w=0;
          for (j = 0; j < n; j++) {
            w+=x[n*j+j];
          }
          if(w!=n*(n*n+1)/2){
            hh=0;
            break;
          }
        }
        if(hh==1){
          w=0;
          for (j = 0; j < n; j++) {
            w+=x[n*j+n-1-j];
          }
          if(w!=n*(n*n+1)/2){
            hh=0;
            break;
          }
        }

        if(hh==1){
          for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
              printf("%d ", x[n*j + k]);
            }
            printf("\n");
          }
          printf("\n");
          cn++;
        }
      }
    }
  }
}


実行結果例
これはすべてのn次魔方陣を求めるソフトです。
何次の魔方陣を発生させるのかをnに入力し
エンターするとn次魔方陣がすべて生成されます。
n=3
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

生成された3次魔方陣は8個です。


            w+=x[n*j+n-1-j];
が大変わかりにくいと思いますが、
トレースするとわかります。n = 3 を前提にトレースします。
j = 0 とき、
            w+=x[3*0+3-1-0];
            w+=x[0+3-1-0];
            w+=x[2];
j = 1 とき、
            w+=x[3*1+3-1-1];
            w+=x[3+3-1-1];
            w+=x[4];
j = 2 とき、
            w+=x[3*2+3-1-2];
            w+=x[6+3-1-2];
            w+=x[6];
ですから、

0 1 2
3 4 5
6 7 8

(数字はgを示す。)
見事に逆対角線上を動いています。
            w+=x[n*j+j];
についても各自でトレースして下さい。



粘り強く待ち続ければ、4次魔方陣でもすべて生成して、
7040個をコンソール画面に表示します。
前に20分程度で全部が生成出来ると書きましたが、
私の記憶違いのようで、実際には今の段階では全部生成するには、
10時間ぐらいかかりそうです。

これからいろいろと改善していく最終的には、
26次魔方陣でさえ1秒で数百の単位で生成できるようにもって行きます。
そこでどのぐらいスピードアップしているのかがわかるように計算にかかった時間がわかるように改善します。
コードは次のようになります。
#include<stdio.h>
#include<time.h> //時間を計測するために必要
void f(int g);
int x[20];
int n, cn;
int main() {
  
clock_t hj,ow; //時刻取得変数の宣言
  printf("これはすべてのn次魔方陣を求めるソフトです。\n");
  printf("何次の魔方陣を発生させるのかをnに入力し\n");
  printf("エンターするとn次魔方陣がすべて生成されます。\n");
  printf("n=");
  scanf("%d", &n);
  cn = 0;
  
hj=clock(); //始めの時刻取得
  f(0);
  
ow=clock(); //終わりの時間取得
  //計算に要した時間を秒単位に換算して表示
  printf("魔方陣生成にかかった時間は%f秒です。\n",(double)(ow - hj) /
1000);
  printf("生成された%d次魔方陣は%d個です。\n", n,cn);
  return(0);
}
以下は同じ
  printf("魔方陣生成にかかった時間は%f秒です。\n",(double)(ow - hj) / 1000);
の1000はミリ秒を秒に換算するために必要なものです。
で実行結果は
これはすべてのn次魔方陣を求めるソフトです。
何次の魔方陣を発生させるのかをnに入力し
エンターするとn次魔方陣がすべて生成されます。
n=3
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

魔方陣生成にかかった時間は0.109000秒です。
生成された3次魔方陣は8個です。

となります。
このできの悪いプログラムでも3次ならおよそ0.1秒ですべて生成できます。

少しずつ改良していって最終的には26次魔方陣でも、
1秒で数百の単位で生成できるように持って行きますが、
この第10講の改良では、4次魔方陣が
021
すべてを約10分程度生成するのが関の山です。
5次魔方陣はおそらく1時間待っても1個も出てこないでしょう。
尚、4次以降では上図のように2桁になりますので、
表示も2桁対応に変更して下さい。

このコードがわかりにくい最大の理由は、
グローバル配列が
int x[25];
と1元配列になっているということです。
皆さん、これを2次元配列
int mah[5][5];
にしてソフトを作り直して下さい。
x座標とy座標を導入しますので、
いままで魔方陣の各値を入力する配列名をxとしてきましたが、
以降はmahに変更します。

第4話へ   第6話へ

002

初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc** c言語 c** 入門 初心者 基礎から応用まで
eclipse c** 入門
魔方陣 数独で学ぶ VBA 入門

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