Существует множество способов собрать кубик Рубика. Алгоритм, который решает головоломку за минимально возможное количество ходов, называют алгоритмом Бога.
Термин «решить головоломку» означает — указать последовательность ходов, переводящих некоторую начальную конфигурацию в некоторую конечную конфигурацию. Оптимально решить головоломку — указать самую короткую последовательность ходов для решения головоломки. Оптимальных решений может быть несколько.
К известным головоломкам, подпадающим под это определение, относятся кубик Рубика, Ханойская башня, Пятнашки, Солитер с фишками (англ.), различные задачи о переливании и перевозке («Волк, коза (овца) и капуста»). Некоторые авторы считают, что алгоритм Бога должен также быть практичным, то есть использовать разумный объём памяти и завершаться в разумное время.
Первые оценки сверху для числа Бога были основаны на «человеческих»
алгоритмах. Вероятно, впервые конкретная оценка сверху была указана Дэвидом Сингмастером в 1979 году. В 1982 году в журнале «Квант» был опубликован список комбинаций, позволяющих решить кубик Рубика в 79 ходов.
Определились два совершенно различных подхода к сборке: «абстрактный» и «конкретный». В первом случае используются многоходовые процессы, которые, казалось бы, не вносят порядка в хаотически разбросанные кубики до последних нескольких ходов.
Алгоритм Марвина Тистлетуэйта.
Марвин Тистлетуэйт специалист по прикладной математике из Лондона, использовал «идеи математической теории групп для компьютерных исследований». Тистлетуэйту принадлежал первый мировой рекорд самого короткого алгоритма приведения куба в порядок всего 52 поворота.
В 2010 г. строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию достаточно не более чем 20 поворотов граней (ходов).