MagicSquare5.py

Pythonで魔方陣5x5全解列挙をやってみた。 以下の条件で10,567秒（約3時間）で全解列挙できた。

• プロセッサ: Intel(R) Core(TM) i7-4500U CPU @ 1.8GHz 1.8GHz（Sony Vaio Pro11 BTO）

• 実装メモリ(RAM): 4.00GB

• OS: Windows 8.1 Pro

• ActivePython 2.7.5.6 (ActiveState Software Inc.) based on Python 2.7.5 (default, Sep 16 2013, 23:11:01) [MSC v.1500 64 bit (AMD64)] on win32

• 標準出力の出力先: 内蔵SSD

• エラー出力の出力先: コマンドプロンプト

  python MagicSquare5.py > d:\output.txt

標準出力に解を出力する。以下の様な行が275,305,224行（二億七千万行）出力される。

dk7j63go5he9b8nai1lfp2mc4

この出力は、以下の魔方陣を意味する。 10～25を'a'～'p'に置換し、一行にする。

13 20  7 19  6  -->  d  k  7  j  6
 3 16 24  5 17  -->  3  g  o  5  h
14  9 11  8 23  -->  e  9  b  8  n  -->  dk7j63go5he9b8nai1lfp2mc4
10 18  1 21 15  -->  a  i  1  l  f
25  2 22 12  4  -->  p  2  m  c  4

標準エラーに10万解ごとに進捗を表示する。

62800000 / 2347.51737175 = 26751.6657195 dk7j63go5he9b8nai1lfp2mc4

• 解の数
• 処理開始からの時間（秒）
• 秒あたりの解の数
• 解

処理が終了すると結果を表示する。

275305224 / 10567.0564106 = 26053.1611928 done.

アルゴリズム

以下のページを参考にさせていただきました。 http://www.guru.gr.jp/~issei/msqj/5houjin2.htm

基本的な考え方

魔方陣は、5×5のマスに1～25の数を1つづつ入れて、5つの行、5つの列、2つの対角線の数の和が同じ（65）になる。 1～25の数から5つ選んで和が65になる組み合わせ（順列ではない）を、ここでは組という。組は1,394通りある。

つまり、魔方陣は1,394 組から、5つの行、5つの列、2つの対角線を選ぶことになる。

本プログラムは、以下の条件1、条件2に該当する行・列・対角線の組み合わせをすべて列挙し、その組み合わせから魔方陣を生成して出力する。

条件1

行・列・対角線の間には以下の関係がある。

• 任意の2つ行の間には、共通する数はない
• 任意の2つ列の間には、共通する数はない
• 2つの対角線の間に、共通する数が1つある
• 任意の行、任意の列の間に、共通する数が1つある
• 任意の対角線、任意の行の間に、共通する数が1つある
• 任意の対角線、任意の列の間に、共通する数が1つある

条件2

魔方陣になるためには、行Aから以下の手順で求めた行Eと、行Aが一致することが必要となる。

1. 行Aと対角線X上で交わる列B
2. 列Bと対角線Y上で交わる行C
3. 行Cと対角線X上で交わる列D
4. 列Dと対角線Y上で交わる行E

AとEが一致する

X  A  A  A  Y <-- AとEが一致する
B  X     Y  D
B     *     D
B  Y     X  D
Y  C  C  C  X

組から魔方陣の生成

ここまでは、各組を構成する数や、行・列・対角線の順序については考慮していない。 最終的には順序を決定すると、魔方陣が完成する。

以下の4つの魔方陣は行・列・対角線の組が共通であり、その1つが魔方陣である場合、残りの3つも魔方陣である。また、それぞれ線対称や90°の単位の回転ではない。

あ い う え お    の に ぬ ね な    き か く こ け    て た つ と ち
か き く け こ    こ き く け か    い あ う お え    え あ う お い
さ し す せ そ    そ し す せ さ    し さ す そ せ    せ さ す そ し
た ち つ て と    と ち つ て た    に な ぬ の ね    ね な ぬ の に
な に ぬ ね の    お い う え あ    ち た つ と て    け か く こ き

左端を基準とすると、左から2番めは「あいうえお」と「なにぬねの」の行を入れ替え、「あかさたな」の列と「おこそとの」の行を入れ替えたもの。

右から2番目は「あいうえお」と「かきくけこ」の行を入れ替え、「たちすてと」と「なにぬねの」の行を入れ替え、「あかさたな」と「いきしちに」の列を入れ替え、「えけせてね」と「おこそとの」の列を入れ替えたもの。

右端は上の2つの置換を両方おこなったもの。

つまり、行・列・対角線の1つの組み合わせから、順序を変えることによって4つの魔方陣が生成できる。

組の表現

組の中では、それぞれの数nを (1 << n) で表す。これを、ここでは「ビット表現」ということにする。 また、出力時に10～25を'a'～'p'に変換する。これを、ここでは「出力表現」ということにする。

 0 --> 0x00000001 --> '-'    ※魔方陣では0は使わない
 1 --> 0x00000002 --> '1'
 2 --> 0x00000004 --> '2'
 3 --> 0x00000008 --> '3'
 :
 9 --> 0x00000200 --> '9'
10 --> 0x00000400 --> 'a'    ※10～25を'a'～'p'で出力する
11 --> 0x00000800 --> 'b'
12 --> 0x00001000 --> 'c'
 :
16 --> 0x00010000 --> 'g'
20 --> 0x00100000 --> 'k'
24 --> 0x01000000 --> 'o'
25 --> 0x02000000 --> 'p'

ビット表現をキーとして、出力表現を値として持つ連想配列bittabを用意する。bittabのキーはひとつのビットしか立っていない整数である。

総和が65の組は、以下のように一つの整数で表現できる。

20 + 19 + 13 + 7 + 6 = 65
   --> 0x001820c0
20 --> 0x00100000
19 --> 0x00080000
13 --> 0x00002000
 7 --> 0x00000080
 6 --> 0x00000040

この表現を使えば、「組Aと組Bに共通の数字がない」という条件は以下のように書くことができる。

(A & B) == 0

「組Aと組Bに共通の数字がひとつだけある」という条件は、ビット表現をキーとする連想配列bittabを使って以下のように書くことができる。

(A & B) in bittab

カブリを避ける

組のビット表現（整数）同士を比較すると大小を判定することができる。 ビット表現の大小に意味はないが、大小関係の順序を固定することによって組み合わせのカブリを防ぐことができる。

例1

行となる5つの組の組み合わせ（順列ではない）を作成するとき、以下の2つの組み合わせは同じものである。

順不同

(20 19 13 7 6)  --> 0x001820c0
(24 17 16 5 3)  --> 0x01030028
(23 14 11 9 8)  --> 0x00804b00
(21 18 15 10 1) --> 0x00248402
(25 22 12 4 2)  --> 0x02401014

ビット表現の大小でソート

(25 22 12 4 2)  --> 0x02401014
(24 17 16 5 3)  --> 0x01030028
(23 14 11 9 8)  --> 0x00804b00
(21 18 15 10 1) --> 0x00248402
(20 19 13 7 6)  --> 0x001820c0

ソート順をビット表現の大小に固定して考えることによって、順序の違いによるカブリを避ける事ができる。

例2

魔方陣を90°回転して行と列を入れ替えても、魔方陣として成立する。 この文書の「基本的な考え方」の行と列の記述を入れ替えても意味は変わらない。

通常の全解列挙では、90°回転した魔方陣はカブリとし、片方のみカウントする。 このため、5つの行、5つの列の合計10組のうち、ビット表現で最大の組は、必ず行に存在するように固定する。 最大の組が列に存在する場合をカウントしないことによってカブリを避ける事ができる。

プログラムの構成

プログラムは、以下の機能を持ったジェネレータを、以下の順序で再帰的に呼ぶ構成である。

1. 5つの行を選ぶ
2. 5つの列を選ぶ
3. 2つの対角線を選ぶ
4. 行と列の順序を確定する

5つの行を選ぶ (genrowメソッド)

行の候補を、集合（set）クラスで持っている。 初期状態ではすべての組（1,394組）が候補である。

その中から1つの行を選ぶと、今の行と他の行は共通する数を持たない（基本的な考え方・条件1）ため、今の行と共通する数を持つ組は、次の行の候補から外れる。

また、順序を固定してカブリを避けるため、選んだ行よりビット表現が大きい組も候補から外れる。

2行目以降も同様に、候補から共通する数字を持つ組とビット表現が大きい組を外していく。候補を絞り込んでいくことにより、試行する場合が限られることになる。

行の候補を次々とビット表現が小さいものに絞り込んでいくので、最初に選んだ行が5つの行の中で最大のビット表現となる。

行の候補が絞り込まれると、候補のなかに含まれない数ができてしまうことがある。その場合は魔方陣を完成するっことができない。候補を絞り込むときは、すべての数が含まれることをチェックし、そうでない場合は探索を打ち切る（枝刈り）。候補の組のビット表現をすべてビットORし、1～25のすべてのビットが1の数と一致することを確認する。

5つの行を選び終えたら、列を選ぶジェネレータを呼ぶ。

5つの列を選ぶ (gencolumnメソッド)

列を選ぶ場合も、候補を集合（set）クラスで持っている。 初期状態ではすべての組（1,394組）が候補である。

行を選ぶとき、列の候補が絞り込まれる。

行と列は共通する数を1つだけ持つ（基本的な考え方・条件1）ため、行を選んだ時点で行と共通する数がない組・共通する数字が2つ以上ある組は列の候補から外れる。

行と列を入れかるタイプのカブリを避けるため、最初の行（最大のビット表現の組）より大きい組も候補から外す。

列を選ぶ処理の中では、行を選ぶ処理と同様の絞り込みがおこなわれる。

選んだ列と他の列は共通する数を持たない（基本的な考え方・条件1）ため、選んだ列と共通する数を持つ組は、次の列の候補から外れる。

順序を固定してカブリを避けるため、選んだ列よりビット表現が大きい組も候補から外れる。

列の候補を絞り込む場合も、行と同様の枝刈りのチェックを行う。

5つの列を選び終えたら、対角線を選ぶジェネレータを呼ぶ。

2つの対角線を選ぶ (gendiagonalメソッド)

対角線を選ぶ場合も、候補を集合（set）クラスで持っている。 初期状態ではすべての組（1,394組）が候補である。

行を選ぶとき、対角線の候補が絞り込まれる。

行と対角線は共通する数を1つだけ持つ（基本的な考え方・条件1）ため、行を選んだ時点で行と共通する数がない組・共通する数字が2つ以上ある組は対角線の候補から外れる。

列を選ぶとき、対角線の候補が絞り込まれる。

列と対角線は共通する数を1つだけ持つ（基本的な考え方・条件1）ため、列を選んだ時点で列と共通する数がない組・共通する数字が2つ以上ある組は対角線の候補から外れる。

対角線同士は共通する数が1つある（基本的な考え方・条件1）ため、1つめの対角線を選んだ時、選んだ対角線と共通する数が1つではない組は、次の対角線の候補から外す。

順序を固定してカブリを避けるため、選んだ対角線よりビット表現が大きい組を次の対角線の候補から外す。

対角線の候補を絞り込んで、2つの対角線が残らない場合は探索を打ち切る。

2つの対角線を選び終えたら、行と列の順序を確定する。

行と列の順序を確定する (gensquareメソッド)

行と列と対角線の組み合わせを選び終えたら、行と列の順序を決定する。

• 2本の対角線の共通の数は、魔方陣の中心のマスの数である 中心の数を含む行は、行0～4の行2とする。 中心の数を含む列は、列0～4の列2とする。

• 中心の数を含まない行は、基本的な考え方・条件2チェックを行う。 条件をみたさない場合は魔方陣が成立しない。 条件をみたす場合は、条件2チェックの行A・行Cを、行0・行4とする。 列B・列Dを、列0・列4とする。

• 残りの2つの行を行1・行3、残りの2つの列を列1・列3とする。

順序が決定したら、それぞれの行と列の共通する数から連想配列bittabを使用して、出力する文字列を生成する。

生成した文字列から文字順を変換して、3つの文字列を生成する（基本的な考え方・組から魔方陣の生成）。

履歴

2014-05-31 Version 1.0 初版公開

以上