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

Алгоритм Бога може існувати для головоломок зі скінченним числом можливих конфігурацій і з скінченним набором «ходів», які допускаються у кожній конфігурації і які переводять поточну конфігурацію в іншу. Термін «розв'язати головоломку» означає — вказати послідовність ходів, що переводять деяку початкову конфігурацію в деяку кінцеву конфігурацію. Оптимально вирішити головоломку — вказати найкоротшу послідовність ходів для вирішення головоломки. Оптимальних рішень може бути декілька.

До відомих головоломок, які підпадають під це визначення, належать кубик Рубіка, Ханойська вежа, П'ятнашки, Солітер з фішками, різні завдання про переливання та перевезення («Вовк, коза і капуста»). Спільним для всіх цих головоломок є те, що вони можуть бути описані у вигляді графу, вершинами якого є всілякі конфігурації головоломки, а ребрами — допустимі переходи між ними («ходи»).

У багатьох подібних головоломках кінцева конфігурація негласно передбачається, наприклад, в «п'ятнашках» — впорядковане розташування кісточок, для кубика Рубіка — однокольоровість граней. У цих випадках «зібрати головоломку» означає, що потрібно для довільної початковій конфігурації вказати послідовність ходів, що приводять у фіксовану кінцеву конфігурацію.

Алгоритм вирішує головоломку, якщо він приймає як вихідні дані довільну пару початкової та кінцевої конфігурацій (або тільки початкову конфігурацію, якщо кінцева конфігурація зафіксована) і повертає як результат послідовність ходів, що переводять початкову конфігурацію в кінцеву (якщо така послідовність існує, в іншому випадку, алгоритм повідомляє про неможливість рішення). Оптимальне рішення містить мінімально можливу кількість ходів.

Тоді алгоритм Бога (для даної головоломки) — це алгоритм, який вирішує головоломку і знаходить для довільної пари конфігурацій хоча б одне оптимальне рішення.

Деякі автори вважають, що алгоритм Бога повинен також бути практичним, тобто використовувати розумний обсяг пам'яті і завершуватися в розумний час.

Нехай G — група перестановочної головоломки (із заданою породжуючою множиною), v — вершина графу Келі групи G. Знайти ефектнивний, практичний алгоритм для визначення шляху із v до вершини v₀, пов'язану з нейтральним елементом, довжина якого дорівнює відстані від v до v₀. […] Цей алгоритм називається алгоритмом Бога.

Оригінальний текст (англ.)

Let G be the group of a permutation puzzle (with a fixed generating set) and let v be a vertex in the Cayley graph of G. Find an effective, practical algorithm for determining a path from v to the vertex v₀ associated to the identity having a length equal to the distance from v to v₀. [...] This algorithm is called God’s algorithm.

— Девід Джойнер[2]

Практичність можна розуміти по-різному. Так, існують комп'ютерні програми, які дозволяють за прийнятний час знайти оптимальне рішення для довільної конфігурації кубика Рубіка[3]. Водночас аналогічна задача для кубика 4 × 4 × 4 на даний момент залишається практично нездійсненною[4][5][6]. Для деяких головоломок існує стратегія, що дозволяє відповідно до простих правил визначити оптимальне рішення вручну, без допомоги комп'ютера.

Альтернативне визначення алгоритму Бога: від алгоритму не потрібно знаходження всієї послідовності ходів; замість цього достатньо знайти перший хід оптимального рішення, що наближує до мети і переводить в нову конфігурацію. Два визначення є еквівалентними: повторне застосування алгоритму до нової пари конфігурацій знову знаходить хід оптимального рішення, що дозволяє отримати всю послідовність ходів оптимального рішення.

Числом Бога даної головоломки називається число n, таке, що існує хоча б одна конфігурація головоломки, оптимальне рішення якої складається з n ходів, і не існує жодної конфігурації, довжина оптимального вирішення якої перевищує n. Іншими словами, число Бога — це точна верхня грань множини довжин оптимальних рішень конфігурацій головоломки.

Число Бога для кубика Рубіка дорівнює 20 — це діаметр графу Келі групи кубика Рубіка[7].

У загальному випадку (для довільної перестановної головоломки), число Бога дорівнює не діаметру графу Келі групи головоломки, а ексцентриситету вершини, що відповідає «зібраному» стану головоломки.

• Кубик Рубіка 3×3×3 завжди може бути вирішене не більше ніж в 20 ходів (Суперфліп[8]), вимагають для збірки не менше 20 ходів. Таким чином, «число Бога» кубика Рубіка дорівнює 20.

• Число Бога кубика Рубіка 2 × 2 × 2 дорівнює 11 ходам, якщо поворот грані на 180° вважається за 1 хід, або 14 ходам, якщо поворот грані на 180° вважається за 2 ходи. Невелика (3674160) кількість конфігурацій кубика Рубіка 2 × 2 × 2 дозволило обчислити алгоритм Бога (у вигляді оптимального рішення для кожної конфігурації) ще в 80-х роках[9].

• Число Бога пірамідки Мефферта дорівнює 11[10].

• Триколірний кубик — кубик Рубіка, протилежні грані якого пофарбовані однаково. Число конфігурацій триколірного кубика дорівнює

${\displaystyle 2^{11}\cdot 3^{7}\cdot C_{12}^{4}\cdot (C_{8}^{4})^{2}=10\ 863\ 756\ 288\ 000}$

У березні-квітні 2012 року було встановлено, що число Бога триколірного кубика дорівнює 15 FTM, 17 QTM або 14 STM (згідно метриці STM, поворот будь-якого середнього шару також вважається за 1 хід)[11].

• П'ятнашки можуть бути вирішені в 80 «коротких»[12] або 43 «довгих»[13] ходів в гіршому випадку (під «короткими» ходами маються на увазі переміщення окремих кісточок, а під «довгими» — переміщення цілих рядів з 1, 2 або 3 кісточок). Для узагальнених пятнашек (з більшим, ніж 15, кількістю кісточок) завдання пошуку найкоротшого рішення є NP-повної[14].

• Для Ханойської вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів зростає експоненціально[15].

• Алгоритм Судного дня
• Кубик Рубіка
• Пірамідка Мефферта

• Кубик Рубіка: штурм твердині (Костянтин Кноп)
• Алгоритм Бога і число Бога (Sliding Tile Puzzle Corner)