第24講 特殊種法で魔方陣を超高速に自動生成する
第１話 特殊種法とは?
今回も
c言語 c++ 入門 初心者 vc++ 使い方 プログラミング 基礎から応用まで
の第19講第1話から引用させて頂きます。
－－－以下引用－－－
第１７講の魔方陣ソフトの改良をもってしても６次以上の魔方陣ではまったく歯が立ちませんでした。
計算量が多すぎて、コンピュータが手に負えなくなってしまうわけです。
６次ですでに３６！＝約3710000000000000000000000000000000000000通りも場合が存在するのですから、
いくらコンピュータといえど、手も足も出ません。
計算量が飛躍的に増えていってコンピュータが手に負えない状態を
計算爆発といいます。
実は、プログラマーはこの計算爆発の問題といつも対峙しているわけです。
プログラマーは計算爆発が起こらないように、常に注意していなければならないのです。
計算量が少なくなるように工夫しなければならないのです。
前のソフトは、すべての場合を調べてしまおうというソフトですが、
このソフトは1000個作成などに限定しても５次が限界です。
何度も紹介してきましたが、
講義が進むと２６次魔方陣でも、１秒に数千個も魔方陣を作成できるようになります。
そこへ向けて講義は進んでいきます。
今回紹介する方法は、私が特殊種法と名付けているものです。
この方法は、数独問題作成ソフトにおいても、基本的には踏襲されています。
基本的にはと書きましたのは、若干改良しているからです。
したがって、数独問題作成ソフトを製作されたい方は、
この講は必読の講となります。
今回の改良によって、７次８次９次１０次あたりが作成可能になります。
さて、特殊種法とは何か。詳しくは、魔方陣の研究（特に、小学生・中学生のための魔方陣授業の第２回、第３回、第４回）を参照していて頂きたいと思いますが、
ここでも簡単に説明しておきます。
５次魔方陣の場合を例に説明しましょう。
| 1 | 7 | 13 | 19 | 25 |
| 18 | 24 | 5 | 6 | 12 |
| 10 | 11 | 17 | 23 | 4 |
| 22 | 3 | 9 | 15 | 16 |
| 14 | 20 | 21 | 2 | 8 |
問題難度が高い理由は、
１から２５までの数字を扱っていることです。
つまり、大きな数字を扱っていることが理由です。
問題が複雑な場合、どうしたらよいでしょうか。
問題を単純化すればよいのです。
数学において問題を簡単にする有用な方法は、
分析による方法です。
分析によって２つの要素に分解すればよいのです。
２要素に分解しやすいように、
すべてのセルから１引いたものを考えておきます。
| 0 | 6 | 12 | 18 | 24 |
| 17 | 23 | 4 | 5 | 11 |
| 9 | 10 | 16 | 22 | 3 |
| 21 | 2 | 8 | 14 | 15 |
| 13 | 19 | 20 | 1 | 7 |
もとの魔方陣に戻すには、
各セルに１加えるだけです。
2要素にするにはどうしたらよいでしょうか。
答えは５進数で表現し直すことです。
例えば、
１９＝３×５＋４
ですから１９は５進数で表現すると、３４となります。
（１×１０＋９から１０進数では１９と表現しました。）
全部５進数で表記し直すと、
| 0 | 11 | 22 | 33 | 44 |
| 32 | 43 | 4 | 10 | 21 |
| 14 | 20 | 31 | 42 | 3 |
| 41 | 2 | 13 | 24 | 30 |
| 23 | 34 | 40 | 1 | 12 |
となります。
さらに、
２要素であることを強調するために
1など1桁を01などと表現し直すと、
| 00 | 11 | 22 | 33 | 44 |
| 32 | 43 | 04 | 10 | 21 |
| 14 | 20 | 31 | 42 | 03 |
| 41 | 02 | 13 | 24 | 30 |
| 23 | 34 | 40 | 01 | 12 |
なります。
さらに、これを5の位の数字と1の位の数字を分けて、
二つの表にします。
| □0□ | □1□ | □2□ | □3□ | □4□ |
| 3 | 4 | 0 | 1 | 2 |
| 1 | 2 | 3 | 4 | 0 |
| 4 | 0 | 1 | 2 | 3 |
| 2 | 3 | 4 | 0 | 1 |
| □0□ | □1□ | □2□ | □3 | □4 |
| 2 | 3 | 4 | 0 | 1 |
| 4 | 0 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 | 0 |
| 3 | 4 | 0 | 1 | 2 |
この二つの表こそが、
5次魔方陣の特殊種（これは私が名付けたもので一般的な使用法ではありません。）です。
なぜ種と名付けているのか。
それは、種を二つ組み合わせれば魔方陣ができるからです。
つまり、二つの表は魔方陣の種（たね）というわけです。
では、特殊の意味は何でしょうか。
これは、魔方陣の種の中でも特殊なものです。
もっと一般的な種も存在するので、
特殊な種（たね）ということで特殊種（とくしゅしゅ）と名付けたわけです。
今回は特殊種による方法なので、１０次あたりまでできるようになるわけですが、
６次魔方陣の場合は、特殊種法ではできないことがオイラーによって証明されています。
６次魔方陣ができるようになるためには、次に学ぶ一般種法が必要です。
特殊種の特殊性とは何でしょうか。
それは各行・各列・各対角線上に０から４までの数字が一つずつ入っていることです。
つまり、各行・各列・各対角線上には同じ数字は重複してはいることはありません。
各行・各列・各対角線にはかならず０，１，２，３，４の５つが入るので合計は自動的にすべて同じ１０になります。
種の考え方は、２４を丸ごと扱ったのでは数字が大きすぎるため場合の数が増えてしまい手に負えなくなるので、
二つの要素、すなわち５の位と１の位の数字に分解し、
それぞれの場合について各列・各行・各対角線の合計が同じになるようにしてから、
それを合体しようということなのです。
つまり、分析と総合です。
この講では、この特殊種をコンピュータに二つ作らせそれを合体することによって、
魔方陣を作成してしまおうというわけです。
作成速度は、５次においてさえ前のソフトより軽く１００万倍は超えるでしょう。
では、皆さんコンピュータに特殊種を作らせるソフトを考えて見てください。
５次なら０，１，２，３，４の５つの数字を各列・各行・各対角線上に一つずつ入れるようにして頂きたいのです。
今回も頭が爆発しそうになるほど難問ですよ。
ヒントは、第１７講の魔方陣ソフトを改良すればよいのです。
ただし、３次魔方陣の特殊種は存在しませんので、４次以上が対象になります。
ｎには４以上代入が前提になります。
－－－以上引用－－－
| □0□ | □1□ | □2□ | □3□ | □4□ |
| 3 | 4 | 0 | 1 | 2 |
| 1 | 2 | 3 | 4 | 0 |
| 4 | 0 | 1 | 2 | 3 |
| 2 | 3 | 4 | 0 | 1 |
| □0□ | □1□ | □2□ | □3 | □4 |
| 2 | 3 | 4 | 0 | 1 |
| 4 | 0 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 | 0 |
| 3 | 4 | 0 | 1 | 2 |
を魔方陣の種（しゅ または たね）と呼びます。
この２つを上の説明の通りに、
合体させると
| 00 | 11 | 22 | 33 | 44 |
| 32 | 43 | 04 | 10 | 21 |
| 14 | 20 | 31 | 42 | 03 |
| 41 | 02 | 13 | 24 | 30 |
| 23 | 34 | 40 | 01 | 12 |
になり、
さらにすべてに１を加え、
１０進数に直し、
普通の表記に戻すと
| 1 | 7 | 13 | 19 | 25 |
| 18 | 24 | 5 | 6 | 12 |
| 10 | 11 | 17 | 23 | 4 |
| 22 | 3 | 9 | 15 | 16 |
| 14 | 20 | 21 | 2 | 8 |
になるというわけです。
つまり、魔方陣の基になるものなので、
魔方陣の種と呼んでいるわけです。
引用では、
| □0□ | □1□ | □2□ | □3□ | □4□ |
| 3 | 4 | 0 | 1 | 2 |
| 1 | 2 | 3 | 4 | 0 |
| 4 | 0 | 1 | 2 | 3 |
| 2 | 3 | 4 | 0 | 1 |
| □0□ | □1□ | □2□ | □3 | □4 |
| 2 | 3 | 4 | 0 | 1 |
| 4 | 0 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 | 0 |
| 3 | 4 | 0 | 1 | 2 |
を特殊種としていますが、
ここでは、すべてに１を加えた
| □1□ | □2□ | □3□ | □4□ | □5□ |
| 4 | 5 | 1 | 2 | 3 |
| 2 | 3 | 4 | 5 | 1 |
| 5 | 1 | 2 | 3 | 4 |
| 3 | 4 | 5 | 1 | 2 |
| □1□ | □2□ | □3□ | 4 | 5 |
| 3 | 4 | 5 | 1 | 2 |
| 5 | 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 5 | 1 |
| 4 | 5 | 1 | 2 | 3 |
を種として扱っていきます。
合成は、一方からは１を引いて５をかけて、そこに他方を加えます。
| 1 | 7 | 13 | 19 | 25 |
| 18 | 24 | 5 | 6 | 12 |
| 10 | 11 | 17 | 23 | 4 |
| 22 | 3 | 9 | 15 | 16 |
| 14 | 20 | 21 | 2 | 8 |
例えば24、を例にしますと、
（5－１）×５＋4＝24
また、を例にしますと
（4－１）×５＋1＝16
です。
種は非常にたくさんあります。
まず、種を自動生成させることから始めることにしましょう。
２次元配列を用意して、それを２次元に配置します。
ただし、６次魔方陣特殊種は存在しないことが、
数学者のオイラーによって証明されていますので、
n=6（nは魔方陣の次数）については規則処理します。
ついでにいうと、
以下では禁則処理をしていませんが、
引用文にもある通りn=3の場合も特殊種は存在しませんので、
本来禁則処理をすべきでしょう。
ここまで講義についてこられた皆さんでも、
いきなりでは難しいですから、
まず対角線を完成させることを目標にしましょう。
