The number of magic squares of order 6

魔方陣全体の集合を小集合に分けるために、いくつかの用語を定義します。

• n次の魔方組 とは、[1..n²]の範囲のn個の異なる整数からなる集合で、要素の和がn次の魔方和( ( n² + 1 ) * n ) / 2に等しいものです。
  • 例:
    • { 2, 9, 4 } は 3次の魔方組です。
    • { 10, 7, 14, 3 } は 4次の魔方組です。
• 異なる正整数の集合{ a₁, a₂, a₃ … }は値が 2^a₁-1 + 2^a₂-1 + 2^a₃-1 + … に等しい一つの整数で表現できます。これを整数集合の2進数表現と呼ぶことにします。
  • 例:
    • { 2, 9, 4 } は 1 0000 1001₂ = 0x10b と表現できます。
    • { 10, 7, 14, 3 } は 0010 0010 0100 0100₂ = 0x2244 と表現できます。

• 異なる正整数の集合の大小関係は、2進数表現の大小で定義することができます。
• 例:
  • 魔方組 { 5, 16, 2, 11 } は魔方組 { 12, 1, 15, 6 } よりも大きいと定義されます。なぜなら、それらの2進数表現は1000 0100 0001 0010 ( = 0x8412 ) と 0100 1000 0010 0001 ( = 0x4821 )であり、0x8412 > 0x4821だからです。

n次魔方陣の要素 x を n² + 1 - x で置き換えることを補数変換と呼び、 魔方組の各要素をすべて補数変換してできる集合は必ず魔方組になります。 このようにしてできる魔方組を元の魔方組の 補数組(complement)と呼びます。

• 4次における例:
  • { 12, 1, 15, 6 } は { 5, 16, 2, 11 } の補数組です。
  • { 7, 10, 3, 14 } は自分自身の補数組です。

2進数表現においては、補数組は 2進数の桁を逆順にすること(bit reversal)で得られます。

• 4次の例:
  • 1000 0100 0001 0010 の補数組は 0100 1000 0010 0001 です。

魔方陣のすべての行と列は魔方組です。ここで 代表魔方組 を 「魔方陣の行魔方組、列魔方組、行の補数組、列の補数組のうち、最大のもの」と定義します。なお、対角列は代表魔方組に関係しないことに注意してください。

例: 魔方陣

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

の代表魔方組は { 16, 13, 3, 2 } = 0x9006であり、これは3列目の補数組です。

魔方陣をその代表魔方組によって小集合に分類します。この分類は魔方陣の回転、反転、M-変換,、補数変換のもとで不変な分類となります。