Использовал Python и двусторонний поиск в ширину, чтобы собрать кубик Рубика 2x2.
Вдохновлен проектом MIT 6.006. Создан с нуля уникально.
https://youtu.be/ZHxLO6fubaU
Создал API куба, алгоритм и графический интерфейс с нуля. На каждой из 6 сторон имеется по 4 разных квадрата, в результате чего получается 24 квадрата. Кроме того, куб состоит из 8 угловых частей, каждая из которых имеет 3 ориентации и, следовательно, соответствует 24 квадратам.
Я определил каждый из 24 подразделов каждой стороны как строку с «xyz» в качестве формата, где x — это цвет, обращенный непосредственно к кубу, а y и z идут по часовой стрелке вокруг куба для этого угла.
Я обошел куб и присвоил каждой стороне фиксированный номер, обозначающий решенное состояние. Например, 0, 1, 2, 3 — это 4 части лицевой белой стороны, где 0 — вверху слева, а остальные идут по часовой стрелке.
На кубике можно выполнить 12 ходов. Справа, слева, сверху, снизу, спереди, сзади. У каждого из них также есть движения против часовой стрелки, поэтому 6x2 = 12 ходов. Каждый из этих 12 манипулирует половиной куба, то есть 12 квадратами. Чтобы сделать эти ходы, я создал словари для каждого из 6 по часовой стрелке, для которых подквадрат поворачивается от исходного к следующему положению. Чтобы сделать простые числа, я просто поменял ключи и значения.
Решение этой задачи особенно сложно из-за огромного количества возможных перестановок куба. Всего 24 подквадрата, получается 24P24 = 24!. Это величина 10^23. В силу определенных ситуаций их меньше этой суммы, но их число по-прежнему огромно.
Чтобы создать дерево, мне пришлось бы выполнить каждый ход и все ходы из ходов, которые становятся очень большими. 12^высота дерева. Мне удалось ограничить этот размер, создав список посещенных позиций, чтобы он не повторял действие для ранее посещенных перестановок.
Я начал с создания односторонней BFS, но это привело бы к пределу рекурсии, поскольку дерево ветвления стало бы слишком большим. Чтобы исправить это, я использовал двустороннюю BFS, поочередно создавая ветки от начала и до конца решения. Он создавал деревья и проверял, нашла ли уже противоположная сторона точку. Если бы это было так, он бы вернул точку соединения.
При этом каждый узел сохраняет своего родителя (для переднего ветвления) или дочернего (для заднего ветвления). Чтобы найти маршрут, я рекурсивно нашел родителя из соединительного узла, а затем всех дочерних элементов этой точки. В результате получился ряд позиций, от запутанных до решенных.
В этом проекте я применил использование теории графов и поиска в ширину . Я улучшил свои навыки в Python и рекурсии. Я также экспериментально обнаружил, что максимальное количество ходов для сборки кубика 2х2 составляет 11 ходов, поскольку мне никогда не удавалось найти решение, которое занимало бы больше времени.
Научились использовать библиотеку tkinter для создания графического интерфейса проекта.
