Shogo's Blog

たぶんプログラミングとかについて書いていくブログ

スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、おねえさんのコンピュータで試す

高校生がスパコンを使って5x5の魔方陣の全解を求めたというニュースをきっかけに、 魔方陣の全解列挙が流行っているようです。

「全解列挙」「数え上げ」「組み合わせ爆発」・・・そして整然とならんだこのマス目・・・ あのおねえさんを思い出しますね。

と、いうわけで、「おねえさんのコンピュータ」の魔方陣版を作ってみました。

「全解列挙をパソコンで試す」の記事と同じような感じで、頭の悪いコードをずらずらと書いてあります。 以下の様な特徴があります。

  • マスを埋める順番はスパコンで求めたものをベース
    • ただし、対称な位置にあるマスを優先(反転・回転の検索を早い段階で打ち切るため)
  • asm.js による最適化!
    • firefoxで特に高速に動作します
    • わかってはいたけど、asm.jsは人間の書くものではない
  • WebWorkerを使った並列計算

実はまだ5x5の計算結果を見てないのですが、 途中までの計算スピードから推測すると十数時間程度で計算が終わるかと・・・。 (Mac Book Air Mid 2012, 4並列)

コンパイルの手間が無いのでお手軽に試せます。 もっと速いマシンでやればすぐに結果がでてくると思うので、みなさんのレポートお待ちしています。

Comments