Собираем кубик Рубика без полного перебора решений

Сколько существует возможных комбинаций кубика Рубика? Как за минимальное количество ходов можно решить эту головоломку? Перебирать все возможные варианты? В этой статье будет представлено два способа решения данной проблемы.

Кубик Рубика имеет конечное количество состояний, поэтому можно составить карту всех комбинаций и решений для них. Тогда при получении кубика в любом состоянии, можно просто следовать уже готовому алгоритму. Это вполне разумный подход, но он требует огромного вложения времени и памяти для построения дерева всех возможных вариантов, хотя и помогает максимально быстро найти решение.

Для предварительного вычислениях всех состояний можно сделать следующее:

1. Начнем с решенного кубика и пометим этот этап как «0».
2. Произведем все простейшие вращения. Полученные состояния отметим как этап «1», а также запишем ходы, которые требуются для возврата к предыдущему состоянию «0».
3. Теперь для всех состояний из «1» произведем простейшие повороты, отметим как «2» и запишем ходы, которые требуются для возврата к предыдущему состоянию «1».
4. Будем повторять до тех пор, пока не найдем все возможные состояния кубика Рубика.

Прим. перев. Простейшим вращением считается поворот одной из граней на 90 градусов по часовой стрелке или против часовой стрелки и поворот грани на 180 градусов. Больше информации о языке вращений кубика Рубика можно найти здесь.

В итоге у вас получится карта всех состояний такого вида:

Это достаточно большое дерево решений, но его глубина — всего 20. Зная этот факт, можно создать улучшенную версию алгоритма, которая будет эффективнее использовать память.

Идея заключается в следующем: нужно создать карту всех состояний кубика, для решения которых требуется 10 ходов. Теперь при получении произвольного кубика Х мы находим такое состояние в дереве, которое можно достичь за еще 10 ходов.

Таким образом, получив комбинацию Х, мы будем следовать тому же самому алгоритму для построения дерева решений. Используя хэш-таблицы можно легко найти комбинацию из предварительно вычисленного дерева. Как только это произошло — решение найдено. Использование поиска в ширину гарантирует минимальное количество ходов для решения комбинации Х.

В криптоанализе такой подход называется «встречей посередине». Он позволяет сократить использование памяти, но увеличивает время расчетов. Теперь вместо огромного дерева можно использовать дерево с меньшей глубиной, затрачивая на решение немного больше времени. Не обязательно делить задачу посередине: в зависимости от доступных ресурсов можно хранить дерево с глубиной 8 или 13.

Представленный алгоритм может быть неэффективен при нынешнем уровне технологий. Команде «God=20» потребовалось огромное количество ресурсов и доля изобретательности, чтобы доказать, что 20 ходов достаточно для решения. Несмотря на это, данный алгоритм работает, и с его помощью можно решить любую комбинацию кубика за минимальное количество ходов.