読者です 読者をやめる 読者になる 読者になる

Folioscope

プログラミング/Unix系/デザイン/CG などのメモがもりもり

5×5魔方陣の全解を求めた記事を読んで

結論

高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 http://www.ccs.tsukuba.ac.jp/pr/media/140228_press

総当たりを14で行いましたが、これが最も少ないかどうかはわかりません。

結論から言うと、14が最小であることはコンピュータによって証明できる。


この記事で着目したいのは、魔法陣の全解を求めたことより、「枝刈り法」によって解を求めたことである。 枝刈り法によって総当りするマスを減らし、計算時間の削減を図った。 つまり25マス全てに総当りせずとも、ある程度数字がマスに入ると、残りのマスも一意に決めることができる。 そして14マスを次の図のように埋めると、チェックがついたマスは一意に決まる。

f:id:ibenza:20140306130054p:plain

なるほど確かに魔方陣が一意に求めることができる. しかし本文で気になる文章が。

総当たりを14で行いましたが、これが最も少ないかどうかはわかりません。

どうやら14が最小であるとは証明されていないようだ。 そもそも数学的に証明できるというのかが謎ではあるが、せっかくなのでコンピュータを使って証明してみたのだ。 コンピュータを使うことで13マスで一意に魔方陣が求まる解を探したが、その解はなし。 また13未満についても存在しないことは、13で見つからないので自明である。 よって高校生が発見した14が最小となる。

ついでに上の図以外のパタンも数えあげてみた。 残念ながら同型の除去を施していないので無駄なものが含まれるが、その数はおよそ820,000と少なくはなかった。 また6x6の魔方陣で一意に決まる最小のマス目を求めようと試みたが*1、 計算時間が5x5の場合と比べ100-1000倍くらいはかかるので、 今はとりあえず諦めた。

*1:23までは確認されている