パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

中学生がスパコンを使って「魔方陣」を解く」記事へのコメント

  • by Anonymous Coward

    この総当りのやり方が面白いですね。自分でオセロの思考ルーチン作ってたころを思い出しました。
    5x5だと枝刈りで総当りのマス目の数を14まで減らせる(残りは自動的に決まる)そうです。
    紙と鉛筆で順にやってみると納得できます。
    こういうのに気付いた時は大興奮だよね!
    参考: http://pc.watch.impress.co.jp/docs/news/yajiuma/20140303_637771.html [impress.co.jp]

    • by Anonymous Coward

      読んでみたら面白かったです。
      アルゴリズムの工夫の醍醐味ですね。

      「中学生がスパコンで解いた(割烹着を着てたかは不明)」
      という成し遂げた人の属性に着目した報道よりも興味深かったです。

      あとは、5×5の全解が判明したことに新規性があるのか無いのかが記事からもニュースリリースからもよくわからなかったのが惜しい。

      • あとは、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 マス調べることには変わりがないのだから、プレスリリースの表現は誤り。

        親コメント
        • by Anonymous Coward

          素人考えだと、線形制約は12個のきがします
          縦5,横5,斜め2.
          独立じゃないのが有るのかな?

          • 各行の制約 5 個を足し合わせると、 25 マスの総和が 325 という制約が出ます。各列の制約 5 個を足し合わせても、同じ制約が出ます。なので、これら 10 個の制約は独立ではなくて、 9 個を満たせば残りの 1 個は自動的に満たされます。

            親コメント
        • by Anonymous Coward

          プレスリリースなんて素人向けなんだから詳しい人がみれば説明が不十分になるのはしょうがないのでは?

          作ってるのも広報担当とかで用語がちゃんとわかってない可能性もあるだろうし。

あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー

処理中...