計算機科学・AIプレプリント理論1分で読めます

巨大ルービックキューブの10⁴⁰の定数を30.5に

50周年を迎えたばかりのルービックキューブは、おそらく世界で最もよく知られたパズルだ。その中心的な問いの一つは、述べるのは簡単だ。最悪の場合、解くのに何手かかるのか? 古典的な3×3×3のキューブについては、答えが正確にわかっている。20手だ。この結果は2014年に、今回の新しい論文の著者の一人であるTomas Rokickiを含むチームが発表した。

もっと大きなキューブ、つまり各辺にn層あるキューブでは、正確な答えには手が届かない。与えられたn×n×nのキューブを最適に解くことは、NP完全でさえある。しかし2011年、Erik Demaineらは最悪の場合がどう増えるかを示した。n² / lg nに比例して増えるのだ。ここでlgは2を底とする対数である。これは、基本的にピースを1つずつ解く標準的な方法より、対数の因子1つ分だけよい。

ばかげた定数をもつ証明

落とし穴があった。2011年の結果が保証していたのは増え方であって、その前につく数ではなかった。そのアルゴリズムを詳しくたどった著者らは、定数が約1.01 × 10⁴⁰になることを見いだした。原因はコンピュータによる確認にある。それは、ある手の組み合わせで24個のピースからなるグループのあらゆる配置に到達できることを証明したが、どれだけ速く到達できるかは示さなかった。その長さについて安全に使える唯一の上界はその配置の集合の大きさ、約3.1 × 10²³ステップで、最終的に式は巨大な数24!(1 × 2 × … × 24、約6.2 × 10²³)を2か所で使うことになる。対照的に、下界、つまりほとんどすべての崩されたキューブに必要な手数の定数は、約12.88と控えめだ。そのためコミュニティの多くは、こうしたアルゴリズムが現実的な大きさで実用になることは決してないと考えていた。

MIT、ミュンヘン工科大学、パロアルトに所属するJeremy Mrzyglocki、Tomas Rokicki、Maxine Perroni-Scharf、Erik Demaineは今回、その定数を明示的で小さなものにした。

キューブのピースのためのソーティングネットワーク

大きなキューブでは、センターピースが大半を占める。その数はn²に比例して増えるが、コーナーとエッジはnに比例する項を加えるだけだ。センターピースは24個ずつのファミリーに分かれ、同じファミリーの中でしか入れ替わらない。基本となる道具は交換子(commutator)だ。A B A′ B′という形の手順で、ほとんどすべてをそのままにして、1つのファミリーの3つのピースだけを入れ替える。チームは、使える4,000通りの3ピース入れ替えすべてについて、それぞれ12手以内の手順を見つけた。

手数を減らすのは2つのアイデアだ。第一に、同じ交換子を、行と列のまとまり全体にわたって、多くのファミリーに同時に適用できる。第二に、各ファミリーを個別に解く代わりに、すべてのファミリーが決まった1つの普遍的な手順(universal sequence)に従って入れ替えを行い、必要のない入れ替えは単に飛ばす。1つの補題がすべてを結びつける。L段の普遍的な手順からは、L/2という主要な定数が得られる。

その手順を短くするために、計算機科学のソーティングネットワークの道具を借りる。ソーティングネットワークとは、どんな入力でも並べ替えられる、比較の固定されたパターンだ。6入力の最適なソーティングネットワークからは96段が得られ、定数は48になる。コンピュータ探索で見つけた、24の位置を12個ずつ、さらに4個ずつのグループに分けるネットワークを使うと、72段(36)まで減る。最後に、3つより多いピースを一度に入れ替える手を許し、位置を別のしかたで分けると、61段まで減る。

30.5という数

定理はこうだ。どんなn×n×nのキューブも、最大で30.5 n²/lg n手に、nが大きければ無視できるようになる項を加えた手数で解ける。定数は3.30 × 10³⁸倍以上改善され、下界の2.37倍以内に収まる(30.5 / 12.88)。準備運動として使われた平らなn×n×1版では、定数が12または18から1.5に下がる。

256層のキューブが解かれていく8つのコマ。展開図と小さなキューブの両方で示され、ランダムな模様から単色へと変わっていく。

1辺256層のキューブを解く過程から、等間隔に取り出した8つのコマ。崩された面が単色に変わっていく。— 図1.1、Mrzyglocki et al. (2026), arXiv:2611.11018.

このアルゴリズムはピースの数に比例する時間で動く。著者らはオープンソースのソルバーを、それが頼っているすべてのネットワークをしらみつぶしに検証するスクリプトとともに公開している。著者ら自身の比較では、およそn = 840から既存のソルバーを上回る。1辺256層と65,536層のキューブを解く様子も描画している。

2.37という数は漸近的な主張だ。式の小さな項は確定していないので、特定のキューブの正確な手数を与えるものではない。著者らによれば、今後の改善は、ピースをソーティングネットワークにまとめる別の方法や、よりよい3ピース入れ替えから得られるかもしれない。そして同じ仕組みで、ほかの巨大パズルや、4次元・5次元のハイパーキューブにも挑めるかもしれない。