第14講 末項確定法による魔方陣自動生成ソフトの高速化
第1話 末項確定法とは?
最近、高校生がスーパコンピュータで5次魔方陣すべてを作り出した
ということが話題になりました。

高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功

上のリンクを参照してください。
このリンクの中で「枝刈り法」と呼んでいる方法が、
私が「末項確定法」と呼んでいるものです。
では、「枝刈り法」とは何でしょうか。
第12講の魔方陣自動生成ソフトにおいて、
高速化するためセル(ます)の入力順は、

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

となっていました。
そして、すべてのセルに1から16までの数字を埋めていき、
すべてのセルで数字の重複テストを行い、
合格した場合に次のセルに進み、

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

色の付いたセルに数字を入力した段階で、
対角線や行や列の合計テストを行い、
すべてのテストをクリアしたものが魔方陣として、
シートにはき出された訳です。
ですが、実は色の付いた番号のセルは、
1から16をすべて確かめる必要はありません。
色の付いたセルのところは自動的に値が決まってしまうからです。
????
ですね。
具体例で説明しましょう。
次のように数字が埋まってきたとき、

   0
0  1
1  2
2 15
3   

右下がり対角線の最後のセルは16に自動的に決定します。
理由は、
34-(1+2+15)=16
です。つまり、最後のセル

  

は試行錯誤する必要がないのです。
ところが、第12講で作った魔方陣自動生成ソフトにおいては、
ここも試行錯誤しています。

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

白以外の色の付いているセルは、
すべて自動決定なので、
試行錯誤する必要はないのですが、
すべて試行錯誤してしまっています。
4次の場合、色の付いているセルは、
8セルですから、全セルの半分です。
つまり、半分ものセルで無駄な試行錯誤をしているのです。
そこで、ここを改良しようというのが
第14講末項確定法という訳です。
尚、「末項確定法」という名称は、
末項(最後のセル)だけは、自動的に決まっている
=確定しているというところから付けました。
公式には「枝刈り法」というそうですが、
私の魔方陣の研究は、
書籍や他のサイトを一切参照しないで独力で研究する
という基本方針で進められていますので、
使っている用語も私独自のものです。
用語は定義さえ明確であれば何でも自由に使えるのです。

実は、様々な工夫をしてきた私からすると、
「枝刈り法」のアイデアしかない高校生が話題になる???
という気もするのです。
もちろん、スーパコンピュータは究極の並列処理ですから、
究極のマルチスレッドプログラミングをした点については、
尊敬の念を持ちますが。
マルチスレッドプログラミングについては、
初心者のためのc++ vc++ c言語 入門 基礎から応用までへ
の該当ページを参照してください。

それでは第12講で作った魔方陣自動生成ソフトを順に改良していきましょう。

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

まず、第1行目の最後から2番目のセル
(4次魔方陣ならセル番号9のセル)において、
無駄な試行錯誤をやめて、
自動決定するように改良しましょう。





第13講第7話へ 第2話へ



トップ

初心者のためのc++ vc++ c言語 入門 基礎から応用までへ
初心者のための excel 2007 2010 2013 vba マクロ 入門 基礎から応用まで
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
vb講義トップへ
VB講義基礎へ
専門用語なしのC++入門へ
専門用語なしのJava入門へ
専門用語なしのVBA入門

数独のページ
魔方陣のページ
数学研究室に戻る
本サイトトップへ