2014年3月21日金曜日

魔方陣

 リンクは貼りませんが、魔方陣の全列挙について、高校生がスパコンで解いたり、それを大人気なくPCベースで実行したりGPGPUやXeonPhiに移植したりしているそうですね。

 さて、ここでは0-1整数線形計画問題に落とし込んで、GLPKで解いてみましょう。全列挙じゃなくて解を一つでも見つけるというだけです。mahoujin.modです。コメント・空行を抜かすとたった20行で表示まで込みで書けました。こういう問題を定式化するにはGLPKのGNU MathProgは非常に強力ですね。実行すると8秒ほどで解が一つ表示されます。もうちょっと頑張って「既に見つけた解以外で」とやることもできるんですが、解の総数が回転・対称解を除いて2億7530万5224通り(Wikipediaより)あるとあって諦めモードです。

 先ほど、8秒と書きましたが、これは--minisatオプションを付けたときの時間です。オプションなし(分枝限定法で解く)と212秒ほどかかります。--minisatオプションは、目的関数が無い実行可能解の探索問題でかつ、0-1整数変数しかないときにしか使えません。しかし、このような問題は魔方陣、数独、ピクロスなどパズル系の問題の定式化に代表される割り当て問題の変形で多く見られます。minisat凄い。

  さて、これだけだと余り面白くないので少しは役に立つことを。
親子方陣というものがあるそうです(Wikipedia:魔方陣、ことバンク参考ページ)。5×5の魔方陣の内側の3×3が魔方陣として成立しているというものです。Wikipedia、参考ページなどによると中心格(要は真ん中)が(1~25の)中心値13のものが知られており、作成法も確立されているそうです。

  しかし、本当に中心格は13じゃないといけないのでしょうか? それ以外の親子魔方陣は無いのでしょうか? 証明はされていないんじゃないでしょうか(書籍までは手を出していないので未確認)。
 というわけで、解いてみました結果は存在しない、ですね。整数線形計画問題やSATではこういう存在しないことの証明も手軽なところが良いですね。

0 件のコメント:

コメントを投稿