去年の記事「ルービックキューブをアルゴリズムで解くということ」に続き，ルービックキューブとアルゴリズム ネタシリーズ第2弾です．
今回は宇宙一無駄な努力をしてルービックキューブを解く方法です．

無駄な努力

スピードキューバ（ルービックキューブを早く解くことを追求する人たち）には常識的に知られていることですが，ルービックキューブは容易に分解できます．

したがって，未完成状態のルービックキューブを分解して，物理的に組み上げることでルービックキューブを完成させることができます．
この一連の操作を目をつぶった状態で実行するとどうでしょうか．
それは多分一生完成しないだろうと予想されるでしょう．全くその通りです．
この手法は言い換えると次のようになります．

アルゴリズムBG:
入力: スクランブルされたキューブ
出力: 完成状態のキューブ
(Step 1) ルービックキューブのパーツを分解する．
(Step 2) 分解したパーツをシャッフルする．
(Step 3) シャッフルされた順にキューブを組み上げていく．
(Step 4) キューブが完成したら終了，完成しない場合 Step 1 に戻る．

コンピュータサイエンスを（ネタ的に）知っている人ならピンとくると思います，これはボゴソートに対応します．

ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。 ボゴソート – Wikipedia より

こんなの終わるわけないやんと思いますが，「無限の猿の定理」により十分長い時間をかければ完成することは示せます．
完成までの試行回数（キューブが組み上げられた回数は）は平均で $ T_{bg} = (8! \cdot 3^{8} \cdot 12! \cdot 2^{12}) / 2 = 259512019646939136000 $ 回です．
これはエッジの位置と向き，コーナーの位置と向きの全パターンの半分です．
平均がなぜ半分でいいのかよくわかりませんが，以下の文献でそう書いてあったので半分にしてます．
参考文献: Bogobogosortについて – w125のブログ

さて，1回キューブを組み立てるのに1分要すると仮定します．
すると完成するのに 259512019646939136000分 かかる計算になります．これは，493744329617464年，すなわち 493兆7443億年です．
ちなみに地球が誕生したのは46億年前，宇宙が生成されたのが138億年前とされています．

以下の文献により，「無限の猿定理」で最も例に取り上げられる，1秒間に10万文字タイプできる猿がハムレットを執筆するのに $ 10^{360790.5} $ 年要するとされていますので，ハムレットを書くのとルービックキューブを揃えるのは確率的にはルービックキューブを揃える方がずっとずっと簡単なのです．
参考文献: 時間の比較 – ニコニコ動画:GINZA http://www.nicovideo.jp/watch/nm16202721

最良で1回の試行回数で完成しますが，この確率は限りなく0に近です．最悪の場合の試行回数は無限大です．

めげない努力

一旦ばらばらに分解してから組み上げるのはさすがに馬鹿すぎるでしょう．
ちゃんとルービックキューブのパズルらしく面を回転させて完成させます．
しかし，回転させるといってもどの面をどの向きに回転させれば揃うのか一向に見当がつきません．

そこでとりあえずやみくもにトライしてみるとします．
この手法は言い換えると次のようになります．

Read more »