Алгоритм Бога

Алгоритм Бога (God's algorithm) является понятием родившимся в ходе обсуждений путей решения головоломки 3х3х3 (кубика Рубика), но также это понятие может быть применено при решении других головоломках и математических игр.

Суть понятия относится к алгоритму, который имеет наименьшее возможное количество ходов для решения. Идея в том, что всезнающий существо (Бог) имеет знание оптимальной  последовательности шагов с любой заданной конфигурации. Максимально возможное число ходов называется «Числом Бога».

Сколько же необходимо сделать движений, чтобы из 43 252 003 274 489 856 000 возможных позиций кубика Рубика собрать его максимально быстро? Вопрос о минимальном и максимальном количестве ходов в Числе Бога долгое время не даёт покоя многим исследователям комбинаторики. Доступного описания «алгоритма Бога» не найдено, а исследования об оптимальной сборке кубика Рубика осуществляются с помощью трудоёмких вычислений. К стоящим упоминания результатам таких исследований относится вывод сделанный  группой учёных использовавших для этого свободное от обработки поисковых запросов машинное время одного из суперкомпьютеров Google Inc.. В 2010 году им удалось доказать, что из любого положения кубик Рубика можно собрать не более, чем за 20 ходов. Точности ради стоит отметить, что этот результат никто не перепроверял из-за сверхзатратности вычислений.

История достижений в поиске числа Бога выглядит так. В июле 1981 года Morwen Thistlethwaite доказывает 52 движений достаточно. Этот результат продержался до декабря 1990 года, когда Hans Kloosterman улучшает его до 42 ходов. В мае 1992 года Michael Reid приводит доказательства, что 39 движений достаточно, но всего одним днём позже Dik Winter снижает количество движений до 37. Продолжая трудиться в этом направлении и используя в анализе двухэтапный алгоритм Herbert Kociemba в январе 1995 года Michael Reid сокращает количество движений в сборке головоломки в верхней границе до 29. В декабре 2005 года Silviu Radu доказывает, что 28 движений достаточно и уже в апреле 2006 улучшает результат до 27 движений. А уже в мае 2007 года Dan Kunkle и Gene Cooperman доказывают возможность решения кубика Рубика за 26 ходов. Tomas Rokicki в марте 2006 года сокращает ещё на одно движение путь к победе. Но Tomas Rokicki и John Welborn уменьшают число сначала до 23 и в том же августе 2008 года до 22 движений. И, наконец, в июле 2010 года группа учёных (Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge) доказывают, что число Бога для кубика Рубика является 20.