Алгори́тм Бо́га — понятие, возникшее в ходе обсуждения способов решения кубика Рубика. Термин может также быть использован в отношении других перестановочных головоломок. Под алгоритмом Бога головоломки подразумевается любой алгоритм, который позволяет получить решение головоломки, содержащее минимально возможное число ходов (оптимальное решение), начиная с любой заданной конфигурации.
Один из пионеров математической теории кубика Рубика Дэвид Сингмастер[1] так описывает появление термина:
Джон Конвей, один из крупнейших специалистов по теории групп в мире, отметил, что Кубик подчиняется так называемым законам сохранения (или чётности), а это означает, что некоторые движения просто невозможны. Либо Конвей, либо один из его коллег в Кембридже определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога».
Алгоритм Бога может существовать для головоломок с конечным числом возможных конфигураций и с конечным набором «ходов», допустимых в каждой конфигурации и переводящих текущую конфигурацию в другую. Термин «решить головоломку» означает — указать последовательность ходов, переводящих некоторую начальную конфигурацию в некоторую конечную конфигурацию. Оптимально решить головоломку — указать самую короткую последовательность ходов для решения головоломки. Оптимальных решений может быть несколько.
К известным головоломкам, подпадающим под это определение, относятся кубик Рубика, Ханойская башня, Игра в 15, Солитер с фишками, различные задачи о переливании и перевозке («Волк, коза и капуста»). Общим для всех этих головоломок является то, что они могут быть описаны в виде графа, вершинами которого являются всевозможные конфигурации головоломки, а рёбрами — допустимые переходы между ними («ходы»).