魔方陣についてコミュの５方陣の自由度は？１３かな？

問題です：
　５方陣の２５個の数字のうち、最小で、何箇所の数字の
配置が決まれば、残りを確定させることができるのでしょうか？

１４個なら十分だというのは下記のようにわかるんだが。

・・・・・・・・・・・例えば：ここから

ＡＢＣＤＥ
ＦＧＨＩＪ
ＫＬＭＮＯ
ＰＱＲＳＴ
ＵＶＷＸＹ

Ａ～Ｙまでの数字が魔方陣を成しているとすると
下記の●の場所は他から算出できる。　

ＡＢＣＤ●・・・→Ｅ＝65-(A+B+C+D)これからU=65-(E+I+M+Q)
●ＧＨＩ●　　以下　BGLQからＶが CHMWからRが UVWXからY
●ＬＭ●Ｏ　　が順次定まり、　AGMＹからＳという具合に
●Ｑ●●Ｔ　　１列中の不確定数が順次、一箇所となって
●●ＷＸ●　　全部の数字が確定する。

・・・・・・・・・・・・・例：ここまで

２５個の変数からなる式で
　５行、５列　２対角の　１２箇所での合計は、それぞれ定和６５に一致することから１２本の連立方程式が得られることとなる。

すると、自由度は２５－１２＝１３となるはずだが？

・・・・・・・あれれ、上の例では１１箇所の●の部分の
　変数しか消去できてないよ？　１個不足かぁ？？　

　１２箇所が不確定ででも、解が得られるようにするには
　●の配置はどうすればいいんだろう？？？？

また、数字の範囲が１から２５に限定されていると
いうことで、もっと自由度減らせないのかなぁ？

　

・・・・・・・・どなたか、コメント下さいな？

コメント(3)

最初
全て
最新の40件

[1] mixiユーザー 04月15日 10:08

また難題をｗ・・・　（；＾＾

あまゐりさん、答え知ってて意地悪してねっすか（爆苦；

今夜、取り組んでみます。

[2] mixiユーザー 04月15日 15:10

自由度をnとすると、５方陣、全探索に要する計算量は

　　概ね25Ｐnつまり２５からｎ個とる順列に比例した
　　計算量を　探索におけるバックトラックでの枝刈り等の
　　効率アップ分で割った値といった具合になるのかなと
　　思います。

大雑把に　楽観的～悲観的に見積もっての想像ですが：

　自由度１０なら数秒～数分～数十分
　自由度１１なら数十秒～数十分～数時間
　自由度１２なら数十分～数時間～数日
　自由度１３なら数時間～数日～数週間
　自由度１４なら数日～数週間～数ヶ月

といったところかなぁと思います。
　自由度は同じでも、ＰＣの性能や、プログラムの
　良しあしで、１０倍～100倍程度の差はでるでしょう。

この自由度１３あたりだと、ＰＣつけっぱなしで放置して
何時間あるいは何日待てるかということで、
　現実的に計算できるか、できないかの微妙なところかと
　思います。プログラムの良し割しで勝負がきまりそうです。

　自由度１２ぐらいなら、１日以内に解が得られるように
なるかとも思うので、答えが１２か１３かは、重大問題です。

[3] mixiユーザー 04月15日 19:08

・・・なんか、勘違いしていたみたい。(o_ _)o～†。

１４が、必要(かつ十分)なのかもしれない。

１２個の連立方程式のうち、少なくとも１本は、他から得ることができるから、独立な式は、実質１１とおりしかなくて、やっぱり自由度は１４ということなのかな。

例えば横５行全部の和は６５ｘ５

　A+B+C+D+E=F+G+H+I+J=K+L+M+N+O=P+Q+R+S+T=U+V+W+X+Y=65
縦４行分の和は６５ｘ４
　A+F+K+P+U=B+G+L+Q+V=C+H+M+R+W=D+J+N+S+X=65

ゆえに、残り縦１行分の和E+J+O+T+Y＝６５なのは自明。
　　

・・・・・・・そうなると、他に探索範囲を絞るには、
　例えば１個目の数字を最初に配置する配置方法で、
　回転・鏡像を除いて考えることにすれば
置き場所は　
　中央／中央の１つ上隣／中央の斜め隣／
　上辺中央／その隣／隅

の計６通り　（これで２５通りより減らせる...)

ハテナ？その各々については、２番目の数字を
どこに配置するかの組み合わせが、また個別に
変わってしまう。これも大変だぁ....(^^ゞ

ログインすると、みんなのコメントがもっと見れるよ