Создание решателя кубика Рубика с помощью Python 3

Привет всем, сегодня мы собираемся создать решатель кубика Рубика с использованием Python 3. В этом блоге я расскажу о теории игр и алгоритмах, необходимых для того, чтобы вы могли легко собрать любой кубик Рубика.

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

Кубик Рубика — это сложные головоломки, которые нужно решить с общим числом возможных комбинаций 43 252 003 274 489 856 000.

Из-за этой сложности кубики Рубика изучают многие, от любителей до математиков. Математикам понравился куб из-за его сложной теории групп, что породило множество научных работ по этой теме.

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

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

Создание куба

Итак, теперь, когда у нас есть базовые знания о кубике Рубика, нашим первым шагом будет его сборка. Ради простоты мы будем придерживаться nxn кубов, чтобы нам не нужно было иметь дело с геометрией каких-либо других трехмерных фигур (иногда головоломка представляет собой другие формы, такие как квадраты или треугольники).

Чтобы построить наш куб, давайте создадим собственный класс для взаимодействия с пользователем. Таким образом, мы можем хранить внутренние состояния в нашем объекте куба, чтобы уменьшить количество переменных, которые необходимо передать каждой функции при манипулировании кубом.

Во-первых, нам нужно определить наиболее эффективную структуру данных для создания нашего куба. Ради этого проекта мы будем использовать трехмерный массив (вложенный список). Я выбрал эту структуру данных из-за необходимых манипуляций с кубом. Используя трехмерный массив, мы можем создавать отображения, чтобы переключать квадраты на места в среднем за время O(n).

Далее нам нужно построить три отдельные функции для управления кубом. С кубиком Рубика вы можете выполнять только три типа возможных ходов.

Все наши функции с тремя движениями используют очень похожий подход. Мы используем отображения, чтобы переключить положение кубов на месте. Для функции вертикального и бокового скручивания мы используем цикл for для прохождения каждой строки столбца, благодаря чему эти функции имеют временную сложность O (n). Однако функция горизонтального скручивания меняет строки местами, что дает временную сложность O (1). Мы также проверяем, нужно ли нам вращать ближайшую грань при каждом повороте. Чтобы повернуть грань кубика Рубика, мы транспонируем соответствующую матрицу.

Решение куба

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

Для решателя есть несколько подходов, которые мы могли бы использовать для решения этой проблемы. Однако мы собираемся использовать подход игрового дерева.

С подходом дерева игры мы знаем, что нам нужно будет искать в дереве игры, чтобы найти наименьшее количество возможных ходов для сборки куба. Однако мы могли бы использовать подход грубой силы, с сегодняшними ограничениями вычислений это невозможно. Вместо этого мы собираемся использовать более эффективный алгоритм поиска.

Мы собираемся использовать алгоритм поиска Итеративное углубление A* (IDA*). Этот алгоритм предпочтительнее A* из-за ограничений памяти. A* и IDA* используют аналогичный подход, при котором A* запоминает, какие узлы были посещены, а IDA* — нет. Обычно A* оптимален для задачи поиска, однако с таким большим пространством поиска очень вероятно, что у нас закончится память, если мы будем использовать A*.

IDA* — это метод поиска по дереву, использующий комбинацию эвристики и поиска в глубину (DFS). В IDA* эвристика направляет DFS с расширением дерева на каждой итерации аналогично поиску по дереву Монте-Карло (см. мою запись в блоге Building a Chess Engine: Part 2 для объяснения MCTS).

Ниже приведен пример дерева для метода IDA*. На этой диаграмме я показываю g_score (стоимость достижения текущего узла) и h_score (прогнозируемая стоимость пути вперед). Этот алгоритм использует простую сумму g_score и h_score для оценки каждого узла.

Как указано ранее в IDA*, мы не сохраняем посещенные узлы. Отсутствие сохранения посещенных узлов имеет свои плюсы и минусы. Не сохраняя посещенные узлы, у нас есть шанс посетить один и тот же узел дважды, что ухудшит временную сложность всего алгоритма. Однако, не сохраняя посещенные узлы, нам не нужно столько памяти. Для нашего варианта использования важна экономия памяти, поскольку мы имеем дело с возможным игровым деревом из 43 252 003 274 489 856 000 узлов.

Хорошо, теперь, когда мы лучше понимаем алгоритм, который собираемся использовать, давайте его создадим. Первое, что нужно будет сделать, это построить нашу эвристику.

Для нашей эвристики мы воспользуемся простым подходом грубой силы и используем алгоритм поиска в ширину для проверки узлов. Здесь мы собираемся хранить различные состояния куба и количество ходов, которые потребовались, чтобы добраться туда из решенного куба, в хеш-таблице. Сохраняя состояния куба в хеш-таблице, мы создали простую таблицу поиска, чтобы узнать, в каком состоянии требуется решить наименьшее количество ходов.

Теперь, когда у нас есть эвристика, мы можем реализовать алгоритм IDA* для решения куба. При построении алгоритма будет использоваться простой алгоритм DFS (поиск в глубину) с описанным выше методом подсчета очков (g_score + h_score). При посещении каждого узла будет передаваться g_score нашего предыдущего узла, чтобы узнать текущую стоимость. Для определения h_score будет выполнен быстрый поиск узла на нашей эвристической карте. Для простоты, если мы найдем узел, которого нет на нашей эвристической карте, мы установим h_score равным 20 (божественное число). Здесь мы могли бы создать несколько дополнительных уравнений, чтобы получить более точную оценку, но для нашего простого варианта использования это не требуется (если у вас есть уравнение для этого, не стесняйтесь оставлять его в комментариях). Со всем этим вместе мы должны получить что-то вроде кода ниже.

Спасибо

Вот и все, мы успешно создали наш решатель кубика Рубика. Вы можете проверить полную версию кода на моем GitHub здесь.

Спасибо за прочтение. Если вам это понравилось, рассмотрите возможность подписки на мою учетную запись, чтобы получать уведомления о моих последних сообщениях.

Ссылка