ルービックキューブの最適解

ルービックキューブの最適解は、ある意味で最も短い解である。解の長さを測る一般的な方法は2つある。1つ目は、1/4回転の数を数えることである。2つ目は、「フェイスターン」と呼ばれる外層のねじれの数を数えることである。外層を同じ方向に2/4回転（90°）回す動きは、1/4回転メトリック（QTM）では2回の動きとしてカウントされるが、フェイスメトリック（FTM、またはHTM「ハーフターンメトリック」、またはOBTM「アウターブロックターンメトリック」）では1回の回転としてカウントされる。^[1]

ルービックキューブを解くのに必要な面回転の最大回数は20回^[2]、1/4回転の最大回数は26回^[3]である。これらの数は、ルービックキューブ群の対応する ケイリーグラフの直径でもある。STM（スライス回転メトリック）では、最小回転回数は不明である。

スクランブルされたルービックキューブを解くアルゴリズムは数多く存在します。最小の移動回数でキューブを解くアルゴリズムは、神のアルゴリズムとして知られています。

3×3×3ルービックキューブの動きを表すために、この記事ではデイビッド・シングマスターが開発した「シングマスター表記法」 ^[4]を使用します。

以下は標準的な移動であり、どの面の中心の立方体をも別の場所に移動しません。

L、R、F、B、U、D の文字は、それぞれ左、右、前、後、上、下の面の時計回りの 1/4 回転を表します。半回転 (つまり、同じ方向に 2 回の 1/4 回転) は、2を付加して示します。反時計回りの回転は、プライム記号( ′ )を付加して示します。

ただし、これらの表記法は人間向けであるため、反時計回りを正とする数学的な表記法ではなく、時計回りを正として使用します。

以下は非標準的な動きです

非標準の移動は通常、上記の標準の移動とは対照的に小文字で表されます。

面の中心立方体を他の場所に移動する:

M、S、E の文字は、中間層の回転を表すために使用されます。M (「Middle」層の略) は、L 面から見て、R 面と L 面の間の層を時計回り (前から後ろへ) に 1/4 回転することを表します。S ( 「 Standing 」層の略) は、F 面から見て、F 面と B 面の間の層を時計回り (上から下へ) に 1/4 回転することを表します。E (「Equator」層の略) は、D 面から見て、 U面とD面の間の層を時計回り (左から右へ) に 1/4 回転することを表します。通常の回転と同様に、2は半回転を意味し、プライム (') は反時計回りの回転を示します。^[5]

代わりに、小文字のr、f、uは、それぞれR 、 F 、 Uと同じ方向に隣接する層を回転させることを示すためにも使用されます。これは予想とより一致しています。^[6]

複数層の立方体では、面名の前に数字が付き、その面から n番目の層の回転を示すことがあります。2R 、2F、2U は、それぞれR、F、Uの隣の層をR、F、Uと同じ方向に回転させるために使用されます。3 層立方体にこの表記法を使用すると、複数層の立方体との一貫性が高まります。^[7]

立方体全体を回転させる:

文字x、y、z は、キューブの回転を表すために使用されます。x は、キューブをR方向に回転することを意味します。 y は、キューブをU方向に回転することを意味します。z は、キューブをF方向に回転することを意味します。 これらのキューブの回転は、アルゴリズムをよりスムーズかつ高速にするためによく使用されます。 通常のターンと同様に、2は半回転を表し、プライム (') は反時計回りの回転を示します。 これらの空間回転は通常、小文字で表されることに注意してください。

引数を数えることで、解決に少なくとも 18 回の手数が必要なポジションが存在することが証明できます。これを証明するには、まず、存在するキューブ ポジションの合計数を数え、次に、解決されたキューブから始めて最大 17 回の移動で達成できるポジションの数を数えます。後者の数はより少ないことがわかります。

この議論は長年改良されなかった。また、これは建設的な証明でもなく、これほど多くの動きを必要とする具体的な局面を示していない。いわゆるスーパーフリップは非常に難しい局面であると推測された。ルービックキューブは、各コーナーピースが正しい位置にあるが、各エッジピースが間違った向きになっているときにスーパーフリップパターンになっている。^[8] 1992年に、20面回転のスーパーフリップの解法がDik T. Winterによって発見され、1995年にMichael Reidによってその最小性が示され、キューブ群の直径の新しい下限が示された。また1995年には、24の4分の1回転でスーパーフリップを解く方法がMichael Reidによって発見され、その最小性がJerry Bryanによって証明された。^[8] 1998年には、解決に24の4分の1回転以上を必要とする新しい局面が発見された。このポジションは「4つのスポットで構成されたスーパーフリップ」と呼ばれ、26回の1/4回転を必要とする。^[9]

最初の上限は「人間」のアルゴリズムに基づいていました。これらのアルゴリズムの各部分における最悪のシナリオを組み合わせると、典型的な上限は約 100 であることがわかりました。

おそらく上限の最初の具体的な値は、1979年初頭にデイビッド・シングマスターが言及した277手である。彼は単にキューブを解くアルゴリズムに必要な最大手数を数えただけだった。 ^{[10] [11]}その後、シングマスターは、エルウィン・バーレカンプ、ジョン・コンウェイ、リチャード・K・ガイが最大160手で済む別のアルゴリズムを考案したと報告した。^{[10] [ 12]}その後すぐに、コンウェイのケンブリッジ・キュービストたちは、キューブを最大94手で復元できると報告した。^{[10] [13]}

「ネストされたサブグループを介した降下」として知られるこの画期的な発見は、モーウェン・シスルウェイトによってなされました。シスルウェイトのアルゴリズムの詳細は、1981 年にダグラス・ホフスタッターによってScientific Americanで発表されました。非常に少ない動きでアルゴリズムを導き出したキューブへのアプローチは、群論と広範なコンピュータ検索に基づいています。シスルウェイトのアイデアは、問題をサブ問題に分割することでした。それまでのアルゴリズムは、キューブの固定されたままにしておくべき部分を見て問題を分割していましたが、シスルウェイトは実行できる動きの種類を制限することで問題を分割しました。特に、彼はキューブ グループを次のサブグループのチェーンに分割しました。

• ${\displaystyle G_{0}=\langle L,R,F,B,U,D\rangle }$
• ${\displaystyle G_{1}=\langle L,R,F,B,U^{2},D^{2}\rangle }$
• ${\displaystyle G_{2}=\langle L,R,F^{2},B^{2},U^{2},D^{2}\rangle }$
• ${\displaystyle G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle }$
• ${\displaystyle G_{4}=\{1\}}$

次に、彼は右剰余類空間のそれぞれについて表を準備しました。各要素について、次の小さいグループに移動するための一連の動きを見つけました。これらの準備の後、彼は次のように作業しました。ランダムな立方体は、一般立方体グループ にあります。次に、彼は右剰余類空間でこの要素を見つけました。彼は、対応するプロセスを立方体に適用しました。これにより、立方体は 内の立方体に移動しました。次に、彼は立方体を、次に、そして最後に に移動するためのプロセスを調べました。 ${\displaystyle G_{i+1}\setminus G_{i}}$${\displaystyle G_{0}}$${\displaystyle G_{1}\setminus G_{0}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle G_{3}}$${\displaystyle G_{4}}$

立方群全体は非常に大きい (~4.3×10 ¹⁹ ) ですが、右剰余類空間ははるかに小さくなります。剰余類空間は最大で、1082565 個の要素のみが含まれます。このアルゴリズムに必要な移動回数は、各ステップの最大プロセスの合計です。 ${\displaystyle G_{0}}$${\displaystyle G_{1}\setminus G_{0},G_{2}\setminus G_{1},G_{3}\setminus G_{2}}$${\displaystyle G_{3}}$${\displaystyle G_{2}\setminus G_{1}}$

当初、シスルウェイトはどんな構成でも最大85手で解けることを示した。1980年1月、彼は戦略を改良し、最大80手で解けるようにした。同年後半には、その数を63に減らし、さらに52に減らした。^[10]コセット空間を徹底的に探索した結果、各ステージの最悪の手数は7、10、13、15で、合計45手であることがわかった。^[15]シスルウェイトのアルゴリズムは、さまざまなコンピュータ言語で実装されている。^[16]

シスルスウェイトのアルゴリズムは、1992 年にハーバート コシエンバによって改良されました。彼は中間グループの数を 2 つに減らしました。

• ${\displaystyle G_{0}=\langle U,D,L,R,F,B\rangle }$
• ${\displaystyle G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle }$
• ${\displaystyle G_{2}=\{1\}}$

シスルスウェイトのアルゴリズムと同様に、彼はキューブをグループ に移動させるために適切な剰余類空間を検索します。次に、グループ の最適解を検索します。とでの検索は、どちらも反復深化 A* (IDA*)と同等の方法で行われました。マイケル・リードが 1995 年に示したように、 での検索には最大 12 手、 での検索には最大 18 手が必要です。キューブをグループ に移動させる準最適解も生成し、 で短い解を探すことで、通常、はるかに短い全体解が得られます。このアルゴリズムを使用すると、通常 21 手未満の解が見つかります。ただし、常にそうなるという証拠はありません。 ${\displaystyle G_{1}\setminus G_{0}}$${\displaystyle G_{1}}$${\displaystyle G_{1}}$${\displaystyle G_{1}\setminus G_{0}}$${\displaystyle G_{1}}$${\displaystyle G_{1}\setminus G_{0}}$${\displaystyle G_{1}}$${\displaystyle G_{1}}$${\displaystyle G_{1}}$

1995 年にマイケル リードは、これら 2 つのグループを使用すると、すべてのポジションを最大 29 回の面回転、または 42 回の 1/4 回転で解決できることを証明しました。この結果は、2005 年にシルビウ ラドゥによって 40 に改善されました。

一見すると、このアルゴリズムは実質的に非効率的であるように見えます。 に18 通りの動き (各動き、その素数、およびその 180 度回転) がある場合、検索しなければならないキューブ状態 (1 京以上) が残ります。IDA*などのヒューリスティックベースのコンピュータ アルゴリズムを使用しても、かなり絞り込むことができますが、これほど多くの状態を検索するのはおそらく現実的ではありません。 この問題を解決するために、Kociemba は の正確なヒューリスティックを提供するルックアップ テーブルを考案しました。^[17] に到達するために必要な動きの正確な数がわかると、検索は事実上瞬時になります。つまり、12 の動きそれぞれに対して 18 個のキューブ状態を生成し、そのたびにヒューリスティックが最も低い状態を選択するだけで済みます。 これにより、 に対する 2 番目のヒューリスティックの精度が低くなりますが、それでも最新のコンピュータで妥当な時間で解を計算できます。 ${\displaystyle G_{0}}$${\displaystyle 18^{12}}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle G_{1}}$

これらのグループ ソリューションをコンピューター検索と組み合わせて使用​​すると、通常、非常に短いソリューションがすぐに得られます。ただし、これらのソリューションは必ずしも最小であることが保証されるわけではありません。最小のソリューションを具体的に検索するには、新しいアプローチが必要でした。

1997年、リチャード・コルフは、ランダムなキューブのインスタンスを最適に解くアルゴリズムを発表しました。彼が作成した10個のランダムなキューブのうち、18回以上の面回転を必要としたものはありませんでした。彼が使用した方法はIDA*と呼ばれ、彼の論文「パターンデータベースを使用してルービックキューブの最適解を見つける」で説明されています。 ^[18]コルフはこの方法を次のように説明しています 。

IDA* は深さ優先探索であり、一連の反復でだんだん長くなるソリューションを探します。長さの下限が現在の反復の境界を超えると、下限ヒューリスティックを使用して枝を切り詰めます。

大まかに言うと、次のように機能します。まず、最適に解決できるほど小さいサブ問題をいくつか特定しました。彼は次のものを使用しました。

1. 立方体は角だけに限定され、端は見ない
2. 立方体は 6 つの辺だけに制限されており、角や他の辺は考慮されません。
3. 立方体は他の 6 つの辺に制限されます。

明らかに、これらのサブ問題のいずれかを解決するために必要な移動回数は、キューブ全体を解決するために必要な移動回数の下限です。

ランダムなキューブ Cが与えられると、反復深化として解決されます。最初に、1 回の移動を適用した結果であるすべてのキューブが生成されます。つまり、C * F、C * U、... 次に、このリストから、2 回の移動を適用した結果であるすべてのキューブが生成されます。その後、3 回の移動などとなります。下限に基づいて、最適な状態を維持するために必要な移動が多すぎるキューブが見つかった場合は、リストから削除できます。

このアルゴリズムは常に最適な解を見つけますが、最悪のケースの分析はありません。このアルゴリズムが最適な解に到達するまでに何回の反復が必要になるかは一般にはわかっていません。このアルゴリズムの実装はここにあります。^[19]

2006年、シルビウ・ラドゥは手法をさらに改良し、どの局面も最大27回の面回転または35回の1/4回転で解けることを証明した。^[20]ダニエル・クンクルとジーン・クーパーマンは2007年にスーパーコンピュータを使用して、未解決のキューブはすべて26手以内（面回転基準）で解けることを証明した。数十億のバリエーションのそれぞれを明示的に解こうとする代わりに、コンピュータはキューブを15,752の状態のいずれかに導くようにプログラムされ、それぞれの状態は数回の追加の動きで解ける。すべて29手で解けることが証明され、そのほとんどは26手で解ける。当初26手で解けなかったものはその後明示的に解かれ、それらも26手で解けることが示された。^{[21] [22]}

トーマス・ロキツキは2008年に計算による証明で、未解決のキューブはすべて25手以内で解けると報告した。 ^[23]これは後に23手に短縮された。^[24] 2008年8月、ロキツキは22手で証明できると発表した。^[25]

最終的に、2010年にトーマス・ロキツキ、ハーバート・コシエンバ、モーリー・デイビッドソン、ジョン・デスリッジは、すべてのキューブの位置は最大20回の面回転で解けるという最終的なコンピューター支援証明を行いました。 ^[2] 2009年にトーマス・ロキツキは、クォーターターンメトリックで29回の移動で、どんなスクランブルキューブも解くのに十分であることを証明しました。^[26]そして2014年にトーマス・ロキツキとモーリー・デイビッドソンは、キューブを解くために必要なクォーターターンの最大数は26であることを証明しました。^[3]

面回転と 1/4 回転の測定基準は、その対蹠点の性質が異なります。^[3] 対蹠点とは、解くのに最大数の動きを必要とする、解から最も遠い混乱した立方体のことです。最大数が 20 である半回転測定基準では、そのような位置が何億もあります。1/4 回転測定基準では、最大 26 の動きを必要とする位置 (およびその 2 回の回転) は 1 つだけ知られています。多大な努力にもかかわらず、1/4 回転距離 26 の位置は他に見つかっていません。距離 25 でも、存在することがわかっている位置 (およびその回転) は 2 つだけです。^{[3] [27]}距離 24 では、おそらく 15 万の位置が存在します。

• シングマスター、デイビッド（1981）。『ルービック マジック キューブに関するノート』Enslow Publishers。

ウィキブックスには「ルービックキューブの解き方」に関する本があります。

• ルービック キューブの解き方。人間が記憶できるほど単純ないくつかのアルゴリズムの概要を説明する Wikibooks の記事。ただし、このようなアルゴリズムは通常、最小限の移動数のみを使用する最適なソリューションを提供しません。