アカウント名:
パスワード:
全パターン、って無限に拡張可能なんだからおかしいだろ
と思ったら、元記事だと25マス（５×５）の場合となっていますね。最も重要な部分落とす編集者って・・・
この記事どこがすごいんだろうなあ、誰でも昔一度は作っていそうな感じだけど。スパコンを使ったところか？
え？さすがに5×5の魔法陣全パターン書いた人は少なくね？
書いたよ。BASICで一晩かかったけど。今のスパコン使っても2時間以上かかることに逆に驚くくらい。
解は2億7,530万5,224通りらしいので、#2555091が言う一晩かけた昔は割と最近のことかな。
一晩が12時間だとして、2億7,530万5,224通りを表示するには1秒に6372.806通り表示しなければならない。5×5の魔方陣なので、1秒間に159,320.152個の数字をディスクに書き込むか画面に表示する必要がある。数字一つに1バイト割り当てると、1274561bps≒1.2Mbps のスループットが要る。
うーん、結果を書き込むだけならATA(1990年代以降）ならぎりちょんか？#これ以外に計算する時間が必要だから、SATA[2000年代以降）でないと無理か？
他の発言にもありますが解の数が2億7350万なのであって、計算量は最悪25の階乗、今回の枝刈り最適化で14個の数字の総当たりということですから計算量はざっと計算して38.8京になると思います。
25! / (25-14)! = 3.88 e+17
※間違ってたらご指摘ください
何も考えない力業のアルゴリズムなら、25の階乗通りなので、かなり効率のいいアルゴリズムじゃなきゃ地球が滅びるまでに終わらなさそう
「何も考えない力業のアルゴリズム」でも枝狩りは出来るから組み合わせはもっと減らせると思う。
例えば、一番上の1列に1,2,3,4,5を置いたら、2列目が16以上になった時点で打ち切ることが出来る。また、縦横斜めで5個数字が並ぶ度に合計を求め、お互いが違う値になっても打ち切ることが出来る。
もちろん、1～25の合計の325を5で割って1列65と分かっているという条件まで使うならば、1列を5個の数字で埋めて65になっていなかったり、途中で66以上になった時点で打ち切ることが出来る。
へー、ぜひソースコードと実行環境を公開して欲しいですね。
確認しますが、「5x5の魔方陣」の「全パターン」ですよね？
最初の一つ目の解が求まっただけでは？
2億以上も解があると知っていなければ解が1つ求まったところでプログラムを終了させている可能性も高い。
http://blog.unfindable.net/archives/7179 [unfindable.net]
上のリンク読む限りだと、まともなコードなら昔のPCでも一晩で出来るってのはホントっぽいね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike
全パターン？ (スコア:5, おもしろおかしい)
全パターン、って無限に拡張可能なんだからおかしいだろ
と思ったら、元記事だと25マス（５×５）の場合となっていますね。
最も重要な部分落とす編集者って・・・
Re: (スコア:0)
この記事どこがすごいんだろうなあ、誰でも昔一度は作っていそうな感じだけど。
スパコンを使ったところか？
Re:全パターン？ (スコア:0)
この記事どこがすごいんだろうなあ、誰でも昔一度は作っていそうな感じだけど。
スパコンを使ったところか？
え？さすがに5×5の魔法陣全パターン書いた人は少なくね？
Re:全パターン？ (スコア:1)
書いたよ。BASICで一晩かかったけど。
今のスパコン使っても2時間以上かかることに逆に驚くくらい。
Re: (スコア:0)
解は2億7,530万5,224通りらしいので、#2555091が言う一晩かけた昔は割と最近のことかな。
Re:全パターン？ (スコア:1)
一晩が12時間だとして、2億7,530万5,224通りを表示するには1秒に6372.806通り表示しなければならない。
5×5の魔方陣なので、1秒間に159,320.152個の数字をディスクに書き込むか画面に表示する必要がある。
数字一つに1バイト割り当てると、1274561bps≒1.2Mbps のスループットが要る。
うーん、結果を書き込むだけならATA(1990年代以降）ならぎりちょんか？
#これ以外に計算する時間が必要だから、SATA[2000年代以降）でないと無理か？
Re: (スコア:0)
他の発言にもありますが
解の数が2億7350万なのであって、計算量は最悪25の階乗、
今回の枝刈り最適化で14個の数字の総当たりということですから
計算量はざっと計算して38.8京になると思います。
25! / (25-14)! = 3.88 e+17
※間違ってたらご指摘ください
Re: (スコア:0)
何も考えない力業のアルゴリズムなら、25の階乗通りなので、かなり効率のいいアルゴリズムじゃなきゃ地球が滅びるまでに終わらなさそう
Re: (スコア:0)
「何も考えない力業のアルゴリズム」でも枝狩りは出来るから組み合わせはもっと減らせると思う。
例えば、一番上の1列に1,2,3,4,5を置いたら、2列目が16以上になった時点で打ち切ることが出来る。
また、縦横斜めで5個数字が並ぶ度に合計を求め、お互いが違う値になっても打ち切ることが出来る。
もちろん、1～25の合計の325を5で割って1列65と分かっているという条件まで使うならば、
1列を5個の数字で埋めて65になっていなかったり、途中で66以上になった時点で打ち切ることが出来る。
Re: (スコア:0)
へー、ぜひソースコードと実行環境を公開して欲しいですね。
確認しますが、「5x5の魔方陣」の「全パターン」ですよね？
Re: (スコア:0)
最初の一つ目の解が求まっただけでは？
2億以上も解があると知っていなければ
解が1つ求まったところでプログラムを
終了させている可能性も高い。
Re: (スコア:0)
http://blog.unfindable.net/archives/7179 [unfindable.net]
上のリンク読む限りだと、まともなコードなら
昔のPCでも一晩で出来るってのはホントっぽいね。