The number of magic squares of order 6

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== 魔方陣数え上げの戦略 =====

用語の定義については [[defintion_of_subsets-j|こちら]]をご覧ください。

=== 2N+2個の魔方組を用意する ====

N次の魔方陣を作るには、以下の制約を満たす合計2N+2個の魔方組(行N個、列N個、対角2個)を用意する必要があります。

    * 行魔方組同士は互いに共通要素を持たない。
    * 列魔方組同士は互いに共通要素を持たない。
    * 各行魔方組は各列魔方組と一つずつ共通要素を持つ。
    * 対角魔方組(候補)は各行魔方組、各列魔方組と一つずつ共通要素を持つ。
    * 対角魔方組(候補)同士は、偶数次の時には共通要素を持たず、奇数次の時には一つだけ共通要素を持つ。

行の組と列の組はそれぞれ大きさの順にソートされた組として生成し、行の順序、列の順序は後で検討するものとします。またこの段階では、対角魔方組の要素は対角線上にあるとは限らず、自由な配置を許すものとし、それゆえに「候補」と呼ばれます。



==== 重複の排除 ====

定義から言って、また効率の面から言っても、回転と反転の自由度から生じる重複は避けなくてはいけません。回転と反転には合わせて8通りの自由度がありますが、それらは以下の3つの操作の組み合わせで作り出すことができます。
  - 主対角線を軸とする反転 (行と列の交換、または転置とも言えます)
  - 水平反転
  - 180度回転(水平反転と垂直反転の同時実行とも言えます)

上記 1.と 2.から生じる重複は、それぞれ以下のような条件を課すことで、除去できます。

  * 最大の行魔方組は最大の列魔方組より大きい
  * 主対角魔方組は副対角魔方組より大きい

変換 3. はM-変換の一部であり、最後の節で議論します。
 
==== 相補対 ====

大部分の魔方陣は補数変換による対を作ります。この対の一方のみを生成し、他方の生成を省略することで数え上げの手間を省くことができます。ただし、補数変換の結果が元の魔方陣と同じになる例外的なケースを正しく扱うよう、注意が必要です。

ここで、3つの場合分けを導入します。魔方陣の行または列をなす最大の魔方組が、行の補数組、列の補数組のうち最大のものと比べて
  - 大きい場合
  - 小さい場合
  - 等しい場合 

1. と 2. のケースは補数変換により互いに1対1に対応するため、1. だけ数えて 2倍することで、2.の数え上げを省略することができます。3. の場合は単にそのまま数え上げます。 

3. のケースがすべて自己補数的だとは限りません。3.のケースをさらに細かく分解してさらに無駄を省くことができるかも知れません。ただしその分解によるオーバーヘッドが大きくならなければです。


==== 効率的な魔方陣の数え上げ ====

上記の条件を満たす 2N+2個の魔方組が与えられたとして、対角魔方組(候補)の要素が正しく配置できるかどうはまだわかりません。我々に残された自由度である、行の並べ替え、列の並べ替えによって魔方陣が構成できるかどうかを調べる必要があります。
      * 列だけを適当に並べ替えることでいつでも主対角要素を正しく並べることができます。
      * その上で、列と行に対して同じ並べ替えを実行しても主対角要素は正しい配置に留まります。 
      * 従って残された問題は:
        * 「行と列に同じ並べ替えを施して、副対角要素を正しく並べられるか?」ということになります。
      * 答えは「場合による」ですが、対称性の議論を使うとうまい判定法が導けます。副対角線は行と列の入れ替えに対して対称であり、行と列に同じ並べ替えを実行してもこの対称性は決して破れません。従って以下の定理が成り立ちます。
        * 副対角候補は、行と列の交換に対して対称な配置にある時にのみ、副対角線上に整列できる。 
      * 対称な配置が常に副対角線に変換できると単純には言えませんが、小さな Nに対して、副対角要素がとりうる対称的な配置を全て調べることは難しくありません。 N=6のとき、そのような配置は {{ :up-diag2.pdf |この15通り}}だけであり、これらはすべて副対角線に変換可能です。従って、(主対角候補を正しく並べるための列の並べ替えを行った後、)副対角候補の配置が行と列の交換に対して対称であることを確認すれば、[[https://oeis.org/A266237|M-変換]]の数だけ魔方陣を見つけたことになります。N=6 における M-変換の自由度は 48です。 
      * 2つ目の節で触れたように、180度の回転による重複は取り除かれるべきです。M-変換の自由度の半分は除去されて24となります。

== 数学(群論)の言葉で言うと  ==

      * 対角候補の要素は各行、各列に1回だけ登場しますから、この配置はN個の対象の入れ替え、すなわち対称群 S<sub>N</sub>の元になります。
      * 主対角候補、副対角候補の配置をそれぞれ d と u とします。これらは S<sub>N</sub>の元です。
      * 主対角候補を主対角線に並べるために列を入れ替える操作は d<sup>-1</sup>をかけることに対応します。この入れ替えによって、dd<sup>-1</sup> = e と ud<sup>-1</sup> が得られます。eは単位元です。
      * この段階での副対角候補の配置 ud<sup>-1</sup> は、副対角線の配置(逆順置換)と同じ共役類に属する時、そしてその時にのみ、副対角線に変換可能です。N=6の時、この共役類はまさに先に示した図で表される 15の元からなります。
      * 実際問題として、置換の共役類は置換の巡回置換型で判定します。副対角線の配置は対象全体の並び順を逆にする置換であり、その巡回置換型は floor(N/2)個の2-巡回と(N mod 2)個の1-巡回からなります。我々はすでに主対角候補と副対角候補が N mod 2 個だけの共通項を持つとことを要請済みなため、1-巡回の個数を確認する必要はありません。結果として、確認すべき条件は長さ3以上の巡回がないことであり、( ud<sup>-1</sup> ) <sup>2</sup> = e または ud<sup>-1</sup> = du<sup>-1</sup> = ( ud<sup>-1</sup> )<sup>T</sup>とも表現できます。