第20講 魔方陣汎用的生成プログラムVer.3=末項確定法
第1話 末項確定法とは?

---以下VC++講義より引用---

今回はいつもと手法を変えて、
最初に、今回の成果を最初に紹介した後に、
末項確定法とは何か説明しましょう。
以下のデータは各次魔方陣を100個作るのにかかった時間です。
入門
1個あたり0.015912秒です。
前話のデータが0.07284秒ですから、約4.6倍のスピード差です。
さらに、10次魔方陣の場合
VBA
1個あたり0.398892秒ですから、約5.6倍です。
今までソフトがバージョンアップする度に、
1万倍とか1100万倍とかとう桁外れの性能アップを見せていたのに比べるとかなり地味に見えるかもしれませんが、
結構大きな戦果だと思います。
プログラミングの世界では、1.1倍でも大きな成果です。
(例えば、数独問題作成ソフトのスピードを1.1倍にするのに私は数日も場合によっては数週間費やしていました。
皆さんからすれば結果だけ見ているので、その苦労は見えないと思いますが、
プログラミングとは地味な研究の積み重ねなのです。
ただ、前々話で紹介したようにときには驚愕の成果を見せることもあります。)
ですから5,6倍はかなり大きな成果です。
さらに、今回の改良によって11次魔方陣も1個あたり約0.056秒でできています。
前話のときは途中で実験を打ち切ってしまったので、単純比較はできませんが、
20秒まで探索範囲を広げて、60分も実験を続けましたが最適乱数系列を発見できませんでしたので、
仮に前話のソフトが20秒であると前提しても、
20÷0.056=約360倍です。
---以上VC++講義より引用---

上の例は、VC++版の場合ですが、Java版でもかなりの高速化が期待できます。
ただし、VC++版では一般種法を先にやってから、末項確定法を適用しています。
一般種法をまだ適応していないJava版では、6次を1個あたり0.015912秒で作ることが出来ません。
しかし、末項確定法の後、一般種法を組み合わせます。
すると同程度の性能を実現できます。


---以下VC++講義より若干内容を変更して引用---

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

末講確定法とは、水色以外のセルについては、初めから入る数字は確定していることに、
着眼した方法です。
例えば、

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

と来たときに、青のセルに入る数字は決まっています。

12
29
39
47
60
72
86
93

(表を見るときには、セルに入っている数字がセル番号のかそのセルに実際に入っている数字かを常に区別してください。
上表の数字は、セル番号ではなく、そのセルに入っている実際の数字です。
本講義においては、セル番号のときは基本的にはピンクとしています。)
1+12+29+39+47+60+72+86+93=439
対角線の合計は、
(1+2+3+・・・+100)÷10={100×(1+100)÷2}÷10=505
ですから、

に入る数字は
505-439=66
と確定してしまうのです。


ですから、このセルについてはfor文で探索するのは無駄です。

に来たら、for文は通らないで次の世界(g+1)に進むか、
前の世界(g-1)に戻るしかないのです。
戻る場合の言うのは、例えば

10
19
28
31
38
52
66
72

なら、1+10+19+28+31+38+52+66+72=317ですが、
合計の45との差をとると、505-317=188

にはいる最大数は100ですから、
このセルのある対角線の合計を505にするのは不可能になっているわけです。
この場合には1つ前のセル

72

に戻ってやり直すしかありません。



あるいは

16
23
36
46
57
69
80
87
95

の場合も16+23+36+46+57+69+80+87+95=509となり、


に入る数字が-4となってしまいこれも禁則に反します。
セルに入る数字は0から9までですから。
この場合にも

95

に戻ってやり直すしかありません。


---以上VC++講義より若干内容を変えて引用---

つまり、末項確定法とは最後の空欄は値が決まっていることに注目した方法です。
末=最後は確定しているので、末項確定法です。
魔方陣の研究においては、残確定法と名付けていましたが、
VC++講義から名称を変更しています。
さて、皆さんVer.2のコードを改良しましょう。



第20講第8話へ 第2話へ

戻る

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

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