Алгоритм Бога (решение за 20 ходов)

05.08.2018
Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.

Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов.

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы доказали, что 20 шагов достаточно для любой позиции.