第５講 問題における数字の配置をいかにするか?
第１話 互いに素について
ここ１０年ぐらいでナンプレ自動生成ソフトの性能が上がったのは、
数理統計学を研究に活かしたからだそうです。
ヒントになる数字を配置するわけですが、
この配置によって出来る確率が決定されています。
よい配置なら短時間で出来る可能性が高くなり、
悪ければ時間をかけても出来ない可能性が生じます。
理想的な配置は全体にヒントが均等に配置される場合です。
例えば、のように偏った配置では下手をすると生成に３０分程度要してしまいます。
では、のように均等に数字を配置するにはどうしたらよいでしょうか。
私は、この配置は整数論を使ってやっています。
整数論といっても中学から高校にかけての整数の単元にすぎず決して難しいものではありません。
皆さん、互いに素ということを学んだことを覚えていますか。
互いに素とは（a，ｂ）を分数a／ｂにしたときに約分できない場合を指します。
言いかえると（a，ｂ）の最大公約数が１であるときに、aとｂは互いに素であるというのです。
ですから、互いに素であるものと互いに素でないものをそれぞれ例示すると、
（５，２）と（６，２）です。
（６，２）の方は最大公約数が２であるのに対して、

（５，２）の方は最大公約数が１ですね。

互いに素である場合に大変面白い性質があり、
それを利用して魔方陣の自動生成に活かしたことがあります。
魔方陣を作成する方法の１つに、
ラテン方陣を２つ作って組み合わせるというものがあります。
ラテン方陣とは数独の素になったもので、
５次ラテン方陣なら１，２，３，４，５という数字が、
すべての行にもすべての列にもひとつずつ並ぶものです。
魔方陣を作成するときには、さらに対角線上にもひとつずつ並ぶものを利用します。
ラテン方陣にしてかつ対角線上にも数字の重複がないものを作り出すことは、
５次や７次なら簡単ですが、４次や６次では難しくなります。
対角線の条件を満たす５次ラテン方陣は次のような簡単な方法で出来ます。
１２３４５という数字を用意しておいて２つずらしを行うだけでできます。

どの行にもどの列にもいずれの対角線上にも、
１から５までの数字がひとつずつ並んでいますね。
２つずらすという意味は１の位置を見ればわかりますね。
２つずつ右にずれていっています。
３つずらしをいっても対角線の条件を満たすラテン方陣になります。

５次魔方陣を作るには、２つの対角線の重複を許さないラテン方陣を次のように合体すればよいのです。
１番目のラテン方陣の各数字に２番目のラテン方陣の同位置の数字から１引いてから５をかけたものを足します。
ピンクのセルを例にすると、
５＋（４－１）×５＝２０
です。すべてのセルについて同じことをやりますと、

という方陣が出来ますが、
これは魔方陣ですね。
どの行合計も列合計も対角線合計も同じ６５になっていますね。
７次魔方陣や１１次魔方陣も同様な方法で簡単にできてしまいます。
ところが、４次や６次などの偶数では同じ方法では出来ないのです。
実際に、１２３４５６という数字を用意して同じことをやってみましょう。

行はもちろんひとつずつ並ぶという条件を満たしていますが、
列は１５３１５３，２６４２６４，３１５３１５，４２６４２６，５３１５３１，６４２６４２
となりいずれも１から６までの数字がひとつずつ並ぶという条件を満たしていません。
３ずらしをしても、

もっとだめになります。どの列にも同じ数字が３回重複してしまいます。

５なら２つずらしや３つずらしをすれば対角線上の数字も重複しないラテン方陣になるのに、
６では列にも対角線にも重複が発生していまいます。
なぜ５と６でこんなに大きな違いがあるのでしょうか。
ヒントは（５，２）と（６，２）です。
２はずらしに対応しています。
５と２は互いに素であるのに対して、
６と２は互いに素ではありません。
対角線の条件を考えなければ５の場合には、
１ずらしでも２ずらしでも３ずらしでも４ずらしでもラテン方陣になるのに対して、
６の場合は１ずらしと５ずらし以外はラテン方陣になりません。
（６，１）と（６，５）は互いに素であるのに対して、
（６，２），（６，３），（６，４）は互いに素ではないからです。
魔方陣場合には対角線上も数字が重複してはならないので、
１ずらしやｎ－１ずらしは最初からだめなのです。
ですから、（６，２），（６，３），（６，４）のようなずらし方でラテン方陣にならなければ、
魔方陣は出来ないのです。

さて、のように均等に配置することと、
互いに素はいかにして結びつくのでしょうか。

トップへ