アカウント名:
パスワード:
到達した状態を管理するのにもメモリが大量に必要になります。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stableって古いって意味だっけ？ -- Debian初級
シミュレーションでは証明にならない (スコア:0)
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
Re:シミュレーションでは証明にならない (スコア:2, すばらしい洞察)
Re:シミュレーションでは証明にならない (スコア:1)
全て揃った状態を、木構造のルートとして、
次の一回の９０度回転操作でできる状態をその子として、
また、次の一回の・・・・・・・・・・・・・・・・・・・・、
を繰り返せば、２６回目の操作までに全ての状態が出現する。
証明終わり。
ところで、ルービックキューブが取り得る状態の数っていくらだ？
６＾５４－回転対称分だから・・・・
ううっ、出直します。
Re:シミュレーションでは証明にならない (スコア:2, 興味深い)
(回した後に回転面を床につければ同じ状態になる)
回す方向は鏡面とすると、無視して考えられる。
最初の一手目は「完成形から一回回した状態」の一パターンしかないので、
完全に揃ってる状態ではなく、一手目を木構造のrootにできるかもしれない、などと思ったり。
#書いた後に不安になってきた。いいのかな？(笑
取り得る状態 (スコア:1)
立方体の合同変換が 6×4 = 24 だから、54!/24 が取り得る状態数。
何か見落としてるような気がするなー。 そうだ、角のcubeは角にしか来れないんだった！
しからば、角のcubeは 8、辺中央のcubeは 12、面中央のcubeは 6
というわけで 8!×12!×6!/24 が取り得る状態数。(ホントにこれで良いのかな？)
実を言うと、ルービックキューブに触ったこともないもんね。
the.ACount
Re:取り得る状態 (スコア:1)
ルービックキューブに触った経験から言うと、
角の1ピースだけが 90度回転するとか、辺の1ピースだけが 向きが反転するとかいった状態は起こらないようです。
Re:取り得る状態 (スコア:0)
よって、エッジとコーナーだけを考えれば良く、位置関係に関しては分解を許せば 12! x 8! 通りありますが、
そのうち半分(奇置換となるもの)は存在しないことが証明可能で他は存在するので、12!x8!/2通り。
エッジの向き(位置は同じでも裏返る場合もある)は、分解を許せば 2^12通りですが、裏返りは実は奇数個にならないことが
分かっているので、2^11通り。コーナーの向きは分解を許せば3^8通りですが、回転数の合計のmod3が0になることが分か
っているので、3^7通り。
よって、 12! x 8! x 2^10 x 3^7 = 43252003274489856000通りで、alchematon氏のコメントにある数字で正しいです。
Re:シミュレーションでは証明にならない (スコア:1, 興味深い)
到達した状態を管理するのにもメモリが大量に必要になります。
逆に不揃いから揃える方向ならば、6面が揃ったというチェックは簡単に実装できます。
また初期状態の全パターンは再帰を使えば簡単に生成できるのでメモリコストは少しですみます。
その各状態から26手まで総当りですが、26手を総当りで試して、26手以内に6面揃えばその初期パターンは26手以内であると確認されるので打ち切れます。
これも再帰を使えば26手までは十分試せるでしょう。
これである初期状態から26手総当りを行っても6面が揃わなければ26手以内では揃わない初期状態があると証明できます。
#どっちにしても計算量は膨大ですね
Re:シミュレーションでは証明にならない (スコア:1)
ルービックキューブの状態を一意で密なハッシュ値であるidに変換できれば
（つまり全ての状態に0から始まる一意なIDが付けられれば）、解を根とする木構造を深さ26までの
深さ優先探索で総当りしながら、たどり着いたノードの状態のハッシュをメモリにキャッシュして、
適当にたまったところでHDDのidビット目に1を上書していけば、最後に全ての状態に対してビットが
立っているか確認するだけでいいので。
ってなわけで問題は結局、
って部分に集約されるのではないかと。
全ての状態に対して到達しているかしていないかを1bitで表したとしても、約5エクサバイト
（43,252,003,274,489,856,000bit）の補助記憶領域が必要な訳で、メモリほど高速である
必要がないのでHDDでOKって事を考えても現実的かは微妙な容量ですね。
ただ、不揃いから揃える場合の初期状態数（43,252,003,274,489,856,000）と、それぞれそこから
下手すると深さが26の木を辿らなきゃいけないって事を考えれば（解からなら1回辿るだけでOK）、
解から辿った方が現実的なやり方だと思います。
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
(というか逆方向を取る時点で枝切りされる)