「ルービックキューブの面を完全にシャッフルするには何回動かせばいいのか？」は数学では超難問

世界中で人気のある「ルービックキューブ」は、初心者には1面をそろえることもかなわないほど難しい立体パズルですが、6面すべてをそろえる世界最速記録はおよそ4秒まで縮まっており、熟練プレイヤーによる研究が日々行われています。しかし、モナシュ大学数学科のティム・ガロニ准教授らによれば、数学の世界ではルービックキューブをそろえるよりも、ルービックキューブの面を完全にシャッフルする方が逆に難しいとのことです。

How hard is it to scramble Rubik’s Cube?
https://theconversation.com/how-hard-is-it-to-scramble-rubiks-cube-129916

「シャッフルしてランダム性を作り出す」ということについては、これまで多くの数学者が研究を行ってきました。スタンフォード大学の数学者であるパーシ・ダイアコニス教授とコロンビア大学の数学者であるデイブ・ベイヤー教授は、「リフルシャッフル」についての研究論文を1990年に発表しています。リフルシャッフルとは、以下のムービーのようにカードをシャッフルするやり方で、ダイアコニス教授とベイヤー教授は「カードの並び順を完全にランダムなものにするためにはリフルシャッフルを7回繰り返すことが必要」と証明しました。

Cardistry for Beginners: Shuffles - Riffle Shuffle Tutorial - YouTube


また、机の上でカードをかき混ぜる場合はどうなるのかについては、以下の記事を読めばわかります。

「カードを机の上でかき混ぜたら何秒で完璧に混ざるのか？」にガチンコで挑む数学者がいる - GIGAZINE

ルービックキューブのパターンは全部で4325京2003兆2744億8985万6000通りも存在しますが、2010年に「ルービックキューブはどんなパターンでもわずか20手以内で必ず解くことができる」ということが証明されました。この「20手」という数字はルービックキューブの世界では「神の数字」と呼ばれています。一方で、「『ルービックキューブをランダムに動かして完全にシャッフルされた状態にするにはどれだけの手数が必要なのか』は非常に難しい問題です」とガロニ准教授は述べています。

ルービックキューブは、3列のうち1列をX軸、Y軸、Z軸のどれかの方向に、90度か180度か270度回転させることが可能。ルービックキューブの面をシャッフルするためには、「15通り(初回は18通り)ある操作のうち1つをランダムに行う」という行為を何度も繰り返す必要があります。ガロニ准教授によれば、「ルービックキューブを完全にシャッフルする」ということは、数学的には「すべてのパターンの出現確率が4325京2003兆2744億8985万6000分の1に限りなく近づくこと」を意味し、この状態を「確率分布が均一である」と呼ぶそうです。

ガロニ准教授によれば、ルービックキューブの操作は「マルコフ連鎖」と呼ばれる確率統計モデルで説明が可能だとのこと。そして、「ルービックキューブで確率分布が限りなく均一になるにはどれだけ操作する必要があるのか」は、アルゴリズムによって確率分布のサンプリングを行う「マルコフ連鎖モンテカルロ法」で確認できるそうです。ただし、3ブロック×3ブロック×3ブロックという一般的なルービックキューブでマルコフ連鎖モンテカルロ法を行うのはあまりにも膨大な計算が必要となるため、記事作成時点では未解決問題となっているとガロニ准教授は述べています。

そこで、ガロニ准教授は「ポケットキューブ」と呼ばれる、2ブロック×2ブロック×2ブロックのルービックキューブで計算を行っています。なお、ポケットキューブの総パターン数は367万4160通りで、「神の数字」は11手です。

by Abdulla Al Muhairi

以下のグラフは、シミュレーションを基にポケットキューブの確率分布を表したもの。横軸のtは手数で、縦軸のd(t)は「均一な確率分布からどれだけ離れているか」を意味しており、d(t)が小さければ小さいほど「よりシャッフルされている」ことを示します。ガロニ准教授によれば、一般的に「よくシャッフルされた」といえるラインはd(t)が0.25を下回った時であり、ポケットキューブの場合はtが19の時。つまり、最低でも19回は操作しなければ、「ポケットキューブをしっかりとシャッフルした」とは数学的にいえないというわけです。

また、手数が増えるほど、確率分布はより均一に近くなるとのこと。25回操作した場合でd(t)は0.092、50回操作した場合でd(t)は0.0012、100回操作した場合でd(t)は0.00000017になるそうです。

なお、ポケットキューブにおけるマルコフ連鎖モンテカルロ法のアルゴリズムは、GitHubで公開されています。