第10講 関数の再帰的使用による魔方陣の自動生成
第7話 魔方陣生成ソフトの改良のヒント

第5話と第6話のコードだと

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

に到達した時点で行合計・列合計・対角線合計が同じになるかを検査していますが、
ここから

1 2 14 16
3 4 5 6
7 8 9 10
11 12 13 15

まではまったく無駄な検索をしています。
この次の

1 2 15 16
3 4 5 6
7 8 9 10
11 12 13 14

においてはじめて1行目の合計が4×(4×4+1)÷2=34になって、
魔方陣の場合の横合計に一致するからです。
検査を
gが15(これは最後のマスに対応します。gは0から始まるからです。)
になった時点で検査していることが問題なのです。

効率的に魔方陣を作り出すためには

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

の数字がgに対応しています。)
の色の付いている部分で検査すべきです。

色の種類が分けてあるのは、

12,15
では対角線合計検査までしなければならないからです。
では、色の付いている段階で検査して
無駄な場合の検索はしないように工夫しましょう。
ノーヒントでは難しいですから、
void f(int g) {
  int i, j, k, h, w, x, y;
//hhは不要なので削除
  x = g / n;
  y = g%n;
  for (i = 0; i<n*n; i++) {
    if (g == 0)mah[x][y] = i + 1;
    h = 1;
    if (g>0) {
      for (j = 0; j<g; j++) {
        if (mah[j / n][j%n] == i + 1) {
          h = 0;
          break;
        }
      }
      if (h == 1)mah[x][y] = i + 1;
    }
    
ここに付け加えコードを入れる。
    付け加えコードではxとyが活躍しますし、
    w=0; とh=0; という命令文が
    全部で4回出てきます。また、
    if (h == 1){
      if(*){
         数行
      }
    }
    も3回現れます。
    w=0; とh=0; という命令文はその3回にそれぞれ1回ずつ登場します。

    if (h == 1) {
      if (g + 1 < n*n) {
        f(g + 1);
      }
      else {
        
for (j = 0; j < n; j++) {
          for (k = 0; k < n; k++) {
            if(mah[j][k]<10)cout<< " " << mah[j][k] << " "; //2桁への対応
            if(mah[j][k]>=10)cout<< mah[j][k] << " "; //2桁への対応
          }
          cout << endl;
        }
        cout << endl;
        cn++;

      }
    }
  }
}
という骨格を示しておきます。
xとyが活躍する理由は

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

にあります。考えてください。
今回の改良による効果は実験していませんが、
おそらく5000倍程度のスピードアップが期待できます。



第6話へ   第8話へ

002

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

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