アカウント名:
パスワード:
この総当りのやり方が面白いですね。自分でオセロの思考ルーチン作ってたころを思い出しました。5x5だと枝刈りで総当りのマス目の数を14まで減らせる（残りは自動的に決まる）そうです。紙と鉛筆で順にやってみると納得できます。こういうのに気付いた時は大興奮だよね！参考: http://pc.watch.impress.co.jp/docs/news/yajiuma/20140303_637771.html [impress.co.jp]
読んでみたら面白かったです。アルゴリズムの工夫の醍醐味ですね。
「中学生がスパコンで解いた（割烹着を着てたかは不明）」という成し遂げた人の属性に着目した報道よりも興味深かったです。
あとは、5×5の全解が判明したことに新規性があるのか無いのかが記事からもニュースリリースからもよくわからなかったのが惜しい。
読売新聞の記事やプレスリリース [tsukuba.ac.jp]には個数がわかっていたと書いてあって、まあ個数だけわかって列挙できないことがないとは言わないけど、この問題の場合は昔から列挙されている。例えば http://www.gaspalou.fr/magic-squares/order-5.htm [gaspalou.fr] を参照。つまり、プレスリリースにある「5×5の魔方陣の全ての解を求めることに成功しました」は嘘ではないけれど、初めて成功したわけではない。
それにしても、このプレスリリースは不正確すぎて頭痛い。
しかし、たとえば5×5の場合、1列の和が65とわかっているため、1列の4マスまで埋まると残り1マスは自動的に求められ、これを総当たりから除くことができます。この考え方を「枝刈り法」といいます。
それは 14 個のマスを総当たりするだけで全部の可能性を調べたことになることの説明であって、枝刈り法の説明ではない。枝刈り法というのは、例えば同ページの図 2 の①から④まで埋めた段階で右下隅のマスが 1 から 25 の範囲を外れていたり、他の既に決まっている数字と重なっていたりした場合に⑤以降を何も試さずにダメと判断して次に進むことを指す。今回の計算でも当然枝刈りはしているだろうから、プレスリリースの説明が変。
今回は総当たりを14で行いましたが、これが最も少ないかどうかはわかりません。さらに減らせる可能性もあります。
これは総当たりするマスの個数が 14 個から減らせるかもしれないと言っているようにしか読めないが、総当たりするマスが 14 マスになるのは 25 個の未知数に 11 個の独立な線形制約があることから 25−11=14 と決まる必然であって、 13 個以下にする方法はない。たぶん、枝刈りをもっと工夫することで、調べる可能性の総数を今より減らせる可能性があると言いたいのだと思うけれど、 14 マス調べることには変わりがないのだから、プレスリリースの表現は誤り。
素人考えだと、線形制約は12個のきがします縦5,横5,斜め2.独立じゃないのが有るのかな?
各行の制約 5 個を足し合わせると、 25 マスの総和が 325 という制約が出ます。各列の制約 5 個を足し合わせても、同じ制約が出ます。なので、これら 10 個の制約は独立ではなくて、 9 個を満たせば残りの 1 個は自動的に満たされます。
プレスリリースなんて素人向けなんだから詳しい人がみれば説明が不十分になるのはしょうがないのでは？
作ってるのも広報担当とかで用語がちゃんとわかってない可能性もあるだろうし。
説明が不十分なら仕方がないと思うけれど、説明が不正確なのは素人向けであっても駄目だと思う。
このての枝刈りだったら、将棋の利かずの駒並べも色々工夫できて面白そうですね。以前脳内で色々考えたことが。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
アルゴリズム (スコア:2, 興味深い)
この総当りのやり方が面白いですね。自分でオセロの思考ルーチン作ってたころを思い出しました。
5x5だと枝刈りで総当りのマス目の数を14まで減らせる（残りは自動的に決まる）そうです。
紙と鉛筆で順にやってみると納得できます。
こういうのに気付いた時は大興奮だよね！
参考: http://pc.watch.impress.co.jp/docs/news/yajiuma/20140303_637771.html [impress.co.jp]
Re: (スコア:0)
読んでみたら面白かったです。
アルゴリズムの工夫の醍醐味ですね。
「中学生がスパコンで解いた（割烹着を着てたかは不明）」
という成し遂げた人の属性に着目した報道よりも興味深かったです。
あとは、5×5の全解が判明したことに新規性があるのか無いのかが記事からもニュースリリースからもよくわからなかったのが惜しい。
Re:アルゴリズム (スコア:3)
読売新聞の記事やプレスリリース [tsukuba.ac.jp]には個数がわかっていたと書いてあって、まあ個数だけわかって列挙できないことがないとは言わないけど、この問題の場合は昔から列挙されている。例えば http://www.gaspalou.fr/magic-squares/order-5.htm [gaspalou.fr] を参照。つまり、プレスリリースにある「5×5の魔方陣の全ての解を求めることに成功しました」は嘘ではないけれど、初めて成功したわけではない。
それにしても、このプレスリリースは不正確すぎて頭痛い。
それは 14 個のマスを総当たりするだけで全部の可能性を調べたことになることの説明であって、枝刈り法の説明ではない。枝刈り法というのは、例えば同ページの図 2 の①から④まで埋めた段階で右下隅のマスが 1 から 25 の範囲を外れていたり、他の既に決まっている数字と重なっていたりした場合に⑤以降を何も試さずにダメと判断して次に進むことを指す。今回の計算でも当然枝刈りはしているだろうから、プレスリリースの説明が変。
これは総当たりするマスの個数が 14 個から減らせるかもしれないと言っているようにしか読めないが、総当たりするマスが 14 マスになるのは 25 個の未知数に 11 個の独立な線形制約があることから 25−11=14 と決まる必然であって、 13 個以下にする方法はない。たぶん、枝刈りをもっと工夫することで、調べる可能性の総数を今より減らせる可能性があると言いたいのだと思うけれど、 14 マス調べることには変わりがないのだから、プレスリリースの表現は誤り。
Re: (スコア:0)
素人考えだと、線形制約は12個のきがします
縦5,横5,斜め2.
独立じゃないのが有るのかな?
Re:アルゴリズム (スコア:2)
各行の制約 5 個を足し合わせると、 25 マスの総和が 325 という制約が出ます。各列の制約 5 個を足し合わせても、同じ制約が出ます。なので、これら 10 個の制約は独立ではなくて、 9 個を満たせば残りの 1 個は自動的に満たされます。
Re: (スコア:0)
プレスリリースなんて素人向けなんだから詳しい人がみれば説明が不十分になるのはしょうがないのでは？
作ってるのも広報担当とかで用語がちゃんとわかってない可能性もあるだろうし。
Re:アルゴリズム (スコア:2)
説明が不十分なら仕方がないと思うけれど、説明が不正確なのは素人向けであっても駄目だと思う。
Re: (スコア:0)
このての枝刈りだったら、将棋の利かずの駒並べ
も色々工夫できて面白そうですね。
以前脳内で色々考えたことが。