ルービックキューブの神の数は20です

ルービックキューブを収集する多くのアルゴリズムがあります-多かれ少なかれ効率的です。 平均的な人間が習得して使用できるものは、通常40以上の動きが必要です。 神のアルゴリズムは、最小数の移動を使用して初期構成を構築するアルゴリズムです（この用語は全知の概念に関連付けられており、他の多くの機械的および論理的なタスクにも使用されます）。 神の数はそれぞれ、最悪の場合にこのアルゴリズムが必要とする動きの数として定義されます。 したがって、ルービックキューブの場合、この数は20です。

ちょっとした歴史

キューブ自体は1974年に発明されました。 立方体の理論的研究は、立方体を解くための最大移動数の下限と上限の評価に焦点を合わせました。



1980年までに、下限は18と推定されました。長さ17以下の大幅に異なる一連の動きは、立方体の構成よりも少ないことが判明しました。 この評価は15年続きました。1995年まで、マイケルリードが「スーパーフリップ」構成（右コーナーと混乱した側面の中間点）には正確に20の動きが必要であると証明しました。



その間、上限の推定値はより頻繁に減少しましたが、よりゆっくりでした：1981年には52でしたが、1995年には同じMichael Reidが値29を取得し、2008年にはTomas Rokickiが25-23-22に減らしましたHabréの記事を受賞しました:-)）、最終的に2010年7月に、同じTomasz RokickiがMorley Davidson、John Dethridge、Herbert Kociembaとともに最終結果-20ムーブを獲得しました。

どうやって？

全部で8つあります！ * 3 ⁷ * 12！ * 2 ¹⁰ = 43,252,003,274,489,856,000〜4.3 * 10 ¹⁹キューブ構成。 対称性とカバーセットを使用して、それらは本質的に異なる構成である55,882,296に削減されました。 各構成のタスクを簡素化するために、彼らは最適なソリューション（それは神のソリューションです）ではなく、20移動以内のソリューションを探しました。



最後に、構成は多くのGoogleコンピューターに分散され、計算はわずか数週間で完了しました。 優れたコンピューター（Intel Nehalem、4コア、2.8 GHz）では、これらの計算には11億秒（35年）かかります。

反応

多くの人がルービックキューブを実用的な価値がないと批判していますが、結果は依然として興味深いものです。少なくともその最終性は、上限も下限もそれ以上移動できないためです。 よく知られている（そして、あなたはキューブが好きでしたか？）オープンな問題は解決されました。研究者を祝福し、他の何かに切り替えることができます。



この結果について学んだ多くの人々が、Googleが癌の問題を解決できるコンピューティングパワーを投入する場所がないと非難していると言っているのは面白いことです。 まあ、誰かが本当にわずか35 CPU年（そして彼らの仕事の数年）で本当に癌治療を見つけることができれば、Googleは彼らに喜んで与えると思います。

ソース

1. 神の数は20

2. ウィキペディアのルービックキューブ

3. redditに関するニュースの議論