20ステップのルービックキューブ
ルービックキューブの任意の位置は、わずか20ステップで解決できます。
数年前、ルービックキューブの23の動きに解決策があることが証明されました。 現在、この数は20に減少しています。これを行うには、Googleから寄付された35（35）年間のコンピューター時間がかかりました。
各ソリューションブロックは独自のアルゴリズムを使用しました。これは、目的の構成を実現するための一連の手順です。 たとえば、1つのアルゴリズムは上面を解決するように設計されており、もう1つのアルゴリズムは中央のエッジを配置するように設計されています。 難易度と必要なステップの数が異なる多くの異なるアルゴリズムがありますが、人々が思い出すことができるものは通常40以上のステップを必要とします。
神は最短のステップ数で問題を解決するより効率的なアルゴリズムを使用できると信じることは理にかなっています。 このアルゴリズムは「神のアルゴリズム」として知られています。 最悪の場合の数は、神の数と呼ばれます。 最終的に、この数は20であることが示されました。
ルービックキューブの発明後、20段階で解決される可能性が高いポジションを見つけるのに15年かかりました。 それから15年後、私たちはどの段階でも20ステップで十分であることを証明します。
1980年までに、下限は18であり、上限はおそらく約80であることが確立されました。以下の表にはすべての結果が含まれています。
ルービックキューブの43 252 003 274 489 856 000 000ポジションをどのように処理しましたか？
大きなタスクを2,217,093,120の小さなサブタスクに分割しました。各サブタスクには19,508,428,800の異なるポジションが含まれていました。 このようなサブタスクの1つは、最新のコンピューターのメモリに簡単に配置できます。この方法により、ソリューションを迅速に取得できました。
ルービックキューブを左右または上下に回しても、実際には何も変わりません。ソリューションのステップ数は同じままです。 これらすべての位置を解決する代わりに、1つの解決策を取得し、回転した位置に拡張することができます。 空間には24の異なる方向があり、各位置にキューブの2つのミラー位置があるため、解決される位置の数は48倍になります。 同様の推論を使用し、「セットをカバーする」問題の検索を使用すると、サブタスクの数は2 217 093 120から55 882 296に減少します。
最適なソリューションには、十分な数のステップが含まれていますが、必要以上のものはありません。 20のステップが必要な1つの位置がすでにわかっているため、各位置に最適なソリューションを検索することはできませんが、20ステップ以下のソリューションのみを検索できます。 これにより、タスクが何度も高速化されます。
Googleの施設で55,882,296個のサブタスクを解決し、すべての計算を数週間で完了する機会がありました。 Googleはコンピューターの特性を公開していませんが、11億秒のコンピューター時間（Intel Nehalem、4コア、2.8 GHz）が計算に費やされました。
私たちは15年間、20ステップを必要とする職種があることを知っていましたが、1つの職位にそれ以上必要なものはないことを証明しました。
20ステップのソリューションを持つポジションはまれですが、実際にそれらを満たすことはかなり可能です。 そのような位置に会う確率は、10 ^（-9）から10 ^（-8）まで異なります。 そのような位置の正確な数は正確にはわかりません。 この表は、各解の長さの位置の推定数を示しています。
16以上の長さの場合、数値は概算です。 私たちの研究では、14行目までのすべての初期データが確認され、15行目は新しい結果です。 8月11日に、ソリューションの長さが20の1,200万のポジションが見つかりました。このポジションは、プログラムにとって最も難しいものでした。
数年前、ルービックキューブの23の動きに解決策があることが証明されました。 現在、この数は20に減少しています。これを行うには、Googleから寄付された35（35）年間のコンピューター時間がかかりました。
各ソリューションブロックは独自のアルゴリズムを使用しました。これは、目的の構成を実現するための一連の手順です。 たとえば、1つのアルゴリズムは上面を解決するように設計されており、もう1つのアルゴリズムは中央のエッジを配置するように設計されています。 難易度と必要なステップの数が異なる多くの異なるアルゴリズムがありますが、人々が思い出すことができるものは通常40以上のステップを必要とします。
神は最短のステップ数で問題を解決するより効率的なアルゴリズムを使用できると信じることは理にかなっています。 このアルゴリズムは「神のアルゴリズム」として知られています。 最悪の場合の数は、神の数と呼ばれます。 最終的に、この数は20であることが示されました。
ルービックキューブの発明後、20段階で解決される可能性が高いポジションを見つけるのに15年かかりました。 それから15年後、私たちはどの段階でも20ステップで十分であることを証明します。
神の数の物語
1980年までに、下限は18であり、上限はおそらく約80であることが確立されました。以下の表にはすべての結果が含まれています。
どうやってやった
ルービックキューブの43 252 003 274 489 856 000 000ポジションをどのように処理しましたか？
- すべてのポジションを2,217,093,120セットに分割しました-各セットで19,508,428,800ポジション。
- セットの対称性とカバレッジに基づいて、ソリューションのセットの数を55,888,296に減らしました。
- 最適なソリューションを探したのではなく、20ステップ以下の長さのソリューションのみを探しました。
- 20秒で1セットの解決策を見つけるプログラムを作成しました。
- 55,888,296セットのすべての構成のソリューションを見つけるには、35年のコンピューター時間がかかりました。
位置空間分割
大きなタスクを2,217,093,120の小さなサブタスクに分割しました。各サブタスクには19,508,428,800の異なるポジションが含まれていました。 このようなサブタスクの1つは、最新のコンピューターのメモリに簡単に配置できます。この方法により、ソリューションを迅速に取得できました。
対称性
ルービックキューブを左右または上下に回しても、実際には何も変わりません。ソリューションのステップ数は同じままです。 これらすべての位置を解決する代わりに、1つの解決策を取得し、回転した位置に拡張することができます。 空間には24の異なる方向があり、各位置にキューブの2つのミラー位置があるため、解決される位置の数は48倍になります。 同様の推論を使用し、「セットをカバーする」問題の検索を使用すると、サブタスクの数は2 217 093 120から55 882 296に減少します。
優れた最適なソリューション
最適なソリューションには、十分な数のステップが含まれていますが、必要以上のものはありません。 20のステップが必要な1つの位置がすでにわかっているため、各位置に最適なソリューションを検索することはできませんが、20ステップ以下のソリューションのみを検索できます。 これにより、タスクが何度も高速化されます。
装備品
Googleの施設で55,882,296個のサブタスクを解決し、すべての計算を数週間で完了する機会がありました。 Googleはコンピューターの特性を公開していませんが、11億秒のコンピューター時間（Intel Nehalem、4コア、2.8 GHz）が計算に費やされました。
最も難しいポーズ
私たちは15年間、20ステップを必要とする職種があることを知っていましたが、1つの職位にそれ以上必要なものはないことを証明しました。
20ステップのソリューションを持つポジションはまれですが、実際にそれらを満たすことはかなり可能です。 そのような位置に会う確率は、10 ^（-9）から10 ^（-8）まで異なります。 そのような位置の正確な数は正確にはわかりません。 この表は、各解の長さの位置の推定数を示しています。
16以上の長さの場合、数値は概算です。 私たちの研究では、14行目までのすべての初期データが確認され、15行目は新しい結果です。 8月11日に、ソリューションの長さが20の1,200万のポジションが見つかりました。このポジションは、プログラムにとって最も難しいものでした。
All Articles