第4講 残確定法によるさらなる高速化
第1話 残確定法の基本的考え方

第2講と第3講のプログラムには大変無駄があります。

 0  1  2  3
 1  ・  ・  ・
 ・  4  ・  ・
 ・  ・ 13  ・
   ・  ・  ・

というのは、ここまで入った時点で(3,3)(すなわちg=3)
に入る数字は自動的に16に決まってしまいます。
対角線合計が34にならなければならないからです。
また

 0  1  2  3
 1  ・  ・  6
 ・  4  7  ・
 ・ 10 13  ・
   ・  ・ 16

でも同様に(3,1)は11に決まってしまいます。さらに、

 0  1  2  3
 1 15  ・  6
 ・  4  7  ・
 ・ 10 13  ・
11  ・  ・ 16

においても(0,2),(3,1),(3,2)も
列合計や行合計が34にならなければならないので、
それぞれ12,5,2と決まってしまいます。
さらに、

 0  1  2  3
 1 15 12  6
14  4  7  ・
 ・ 10 13  ・
11  5  2 16

(2,3),(1,3),(2,3)も同様にそれぞれ
8,9,3と決まってしまいます。

したがって、

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

4次魔方陣なら計8箇所もループ文が必要としないところで
ループしていたのです。
本来なら8次元ループで済むところを16次元ループしていたのですから、
如何に無駄が多いかわかります。

そこで、gの番号を

 0  1  2  3
 0  6  ・  3
 7  1  4  ・
 ・  5  2  ・
 ・  ・  ・  ・

と付け加えて根本から作り直すのも1つの手ですが、
番号付けが複雑になりすぎるという点と、
今まで作った資産を活かすという観点から
若干の改良のとどめ、
残確定法1としましょう。
(4次魔方陣なら8カ所からの残りの8カ所を決めるということで、
この方法を残確定法と名付けたいと思います。)

プログラムの解説は次話としたいと思います。

以上の改良によってさらなる高速化が実現し7次魔方陣までが可能になりました。
講義が進むとより高速化が図られ、やがては18次魔方陣あたりでも、
1秒で100個ぐらい作れるようになります。
是非とも今後とも講義にお付き合い願えればと思います。


第3講第6話へ
 第4講第2話へ


VB入門講義応用編トップへ

VB入門講義トップへ