４次の魔方陣

４次の魔方陣を数える

３次の魔方陣は対称・回転を除くと１個のみですが、４次以上の正魔方陣は多数出現します。これはコンピュータを使えば簡単に(??)各次元のものを網羅させることができます。むろん次元が多くなるほど計算にかかる時間もどんどん増えて行きますが。。。。

という訳で、以前のサイトにこのページがあった時、４次の魔方陣は846種類です、などと書いたら http://www.guru.gr.jp/~issei/の沼田さんから「違います。880種類です」との訂正の指摘を頂きました。沼田さんありがとうございます。

なかなかプログラムを見直す機会が無かったのですが、ここに引っ越すのを機に見直しまして、正しく880種類を得ることができました。

この結果はこちらにあります。興味のある方は見てみて下さい。

見つけだすロジック

自分でこういうソフトを組んでみたい人に少しでも参考になるように、一応私が作ったソフトのロジックの概要を書いておきます。

一番単純な考え方としては、４次の魔方陣は16個の数字を並べて作る訳ですから、16個の数字の配列を全部生成させて、それをいちいち魔方陣ができてるかどうか調べていけば、全てを網羅することができます。たとえばこんなことをすればいいわけです。

    for (i0=1; i0<=16; i1++)
      for (i1=1; i1<=16; i1++)
        for (i2=1; i2<=16; i2++)
          for (i3=1; i3<=16; i3++)
            for (i4=1; i4<=16; i4++)
              for (i5=1; i5<=16; i5++)
                for (i6=1; i6<=16; i6++)
                  for (i7=1; i7<=16; i7++)
                    for (i8=1; i8<=16; i8++)
                      for (i9=1; i9<=16; i9++)
                        for (ia=1; ia<=16; ia++)
                          for (ib=1; ib<=16; ib++)
                            for (ic=1; ic<=16; ic++)
                              for (id=1; id<=16; id++)
                                for (ie=1; ie<=16; ie++)
                                  for (ig=1; ig<=16; ig++)
                                  {
                                      if (Check(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,ia,ib,ic,id,ie,ig))
                                        Store(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,ia,ib,ic,id,ie,ig);
                                  }

しかし、こんなことをしますと、ループは16¹⁶=1.8×10¹⁹回になってしまいますので、１ループを仮に１μ秒で処理できたとして、処理時間は58万年!!ほど掛かってしまいます。

ということで、現実的にはこんなやり方はできないという訳です。そこで少し頭を使う必要があります。

実は、４次の魔方陣はその中の８個の数字で完全に決定します。下記で[ ]をつけたものは他の数字から計算できます。

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

実際、
  a[ 3]=34-(a[0]+a[1]+a[ 2])
  a[ 7]=34-(a[4]+a[5]+a[ 6])
  a[12]=34-(a[0]+a[4]+a[ 8])
  a[ 9]=34-(a[3]+a[6]+a[12])
  a[13]=34-(a[1]+a[5]+a[ 9])
  a[14]=34-(a[2]+a[6]+a[10])
  a[15]=34-(a[12]+a[13]+a[14])

ですから、実は、この処理は16個の数字から8個並べる配列P(16,8)=5,1891,8400回実行すれば済むのです。

この回数なら、１ループを先ほどの計算の10倍の10μ秒かかったとしても 5189秒で済んでしまうことになります。これなら何とかなります。

しかし、実はもう少し単純化することができます。

第一に先頭が9以上の配列は調べる必要がありません。

それはひとつ魔方陣が得られますと、その各数字を 17-x したものも魔方陣となりますので、8以下のものだけ調べて網羅すれば全ての場合が得られることになります。これで調べる回数は半分の2,5945,9200にすることができます。（むろんひとつ得られたら、その回転・反転と上記補数のものも数えておく訳です）

そして更に、回数は減らせます。つまり魔方陣は全ての数字を並べてからチェックするのではなく、並べている途中でも「もうダメ」という場合があります。つまり、４個の数字の和が34にならなければならないわけですから、最初の３個の数字の合計が17〜33の間に納まっていないと、どうにもなりません。そういう訳で、処理を途中で中断できる場合がかなりあります。これは下記の場所でチェックできます。

　[2] 横のチェック
　[6] 横のチェック
　[8] 縦のチェック
　[10] 縦および斜めのチェック

こういう処理はPrologueなどではカットと言うのですが、このカットを入れることにより、私のプログラムではループ回数を3749,9044回と、１桁小さくすることができました。このソフトを133MHzのPentiumで実行したところ処理時間は94秒。１ループに約２．５μ秒かかったことになります。

なお、実際にはテーブルは内部的に下記のように設定しました。

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

それから、数字の重複チェックは、その前の数字をループしてチェックするのではなく、そこまでの間に使用した数字にフラグを付けて置いて、そのフラグを見て、使用済みかどうかをチェックする方式で行いました。こういうプログラムを作る時の基本は『如何にしてループを無くすか』です。

また、８個の数字の配列から魔方陣を作っていますので、生成する時に使用した列は完成後チェックする必要がありません。実際問題として、この生成方法でチェックが必要なのは右端の縦の列と、０→１５側の斜めのみです。

（※しかし。。。４次で94秒掛かっていては、５次に進めないなぁ。。。多分、できあがった魔方陣自体の重複チェックが遅いのかも。何も考えてないからなぁ。。。）

---