Постановка задачи

Вы умеете собирать кубик Рубика? Я практически нет. В детстве я мог собрать только пирамидку, а кубик просто раздирал на запчасти и собирал заново, после чего он стремительно разбалтывался. В прошлом году я съездил на сигграф и там на одном из выставочных стендов раздавали (ужасные по качеству, но зато с рекламой) кубики, после чего конференция для меня была практически потеряна, зато двенадцать часов в самолёте прошли незаметно.

Собирать кубик, подглядывая в уже готовые алгоритмы, мне было неинтересно, поэтому я его собрал пока что только один раз, это у меня заняло примерно полгода и приличную стопку исписанной бумаги. Между делом мне на глаза попался проект MindCub3r. Его автор даёт чертежи и ПО для роботов-сборщиков кубика из LEGO, причём эти чертежи есть для всех возможных комплектов, начиная от первого NXT и заканчивая EV3.




Эти роботы крайне хороши, я восхищён тем, их автор David Gilday использует для непосредственно сборки кубика только два сервомотора и ещё один для сканера. Надо учитывать, что стандартные наборы LEGO довольно скудны, и то, что такого робота можно собрать из одной коробки — это немалое достижение. Работает оно просто, сначала кубик сканируется: его датчик ставится напротив каждой этикетки кубика, затем софт решает кубик, выдавая цепочку необходимых вращений, которая потом и исполняется механически.

Решил я повторить этого робота, для начала мне просто хотелось получать собранный кубик, а задача максимум — это задать роботу нужную мне конфигурацию (не обязательно собранный кубик) и получить её на физическом кубике. Это мне позволит получить своего рода сейв, когда я буду собирать кубик вручную, и я смогу к нему вернуться в любой момент (вы помните, что я не хочу смотреть в готовые алгоритмы сборки, мне интересно научиться собирать самому?) На данный момент я записываю все ходы на бумаге, чтобы иметь возможность откатиться, и мне это порядком надоело.

Итак, собрал я хардварную часть робота, сборочные чертежи великолепны. Скачал софт, загрузил, с трепетом поставил кубик на платформу и жестоко обломался. Оказывается, этому роботу необходим официальный кубик Рубика, а я купил тот, что используется для спидкубинга. У него другие цвета граней (например, нет белого), и робот надорвался, не сумел его сосканировать. Хорошо, сказал я, поскрёб по сусекам, нашёл официальный кубик, правда, возрастом под два десятка лет. С его затёртыми и залапанными наклейками робот тоже работать не захотел.



Ну что ж, всё равно мне пришлось бы рано или поздно совать нос в код, т.к. родной софт майндкубера умеет только собирать полностью, но не умеет собрать отдельную конфигурацию. Исходники под NXT опубликованы, а вот под EV3 я их не нашёл. Мне удалось поправить только сканирующую фазу для NXT, обновлённые роботы спокойно собирали и мой спидкубик, и официальный, что я привёл на фотографиях выше. Но в итоге тесниться в NXT мне надоело, там оказалась съеденной почти вся память, поэтому я решил писать код с нуля под EV3.

Итак, постановка задачи: написать весь софт под существующий хард MindCub3r EV3, для начала софт должен просто собирать кубик. Минимизировать количество ходов в сборке меня не интересует, мне нужен как можно более простой код. Эта статья говорит только про то, как решать кубик, в следующей я опишу сканирование и управление сервами. В среднем решение получается длиной слегка за сто ходов.

Пишем код

Использованный метод

В мире огромное количество алгоритмов, наверное, самым правильным было бы запрограммировать вот этот. Но это надо думать, изобретать эвристики для A* с итеративным заглублением, а я ленивый. Кроме того, это надо думать, как его использовать, чтобы получить заданную конфигурацию, а я ленивый. Поэтому я буду пользоваться самым тупым и прямым методом: при помощи Cube Explorer записываем все последовательности поворотов, которые позволяют собрать

• нижнее переднее ребро
• нижний правый передний угол
• переднее правое ребро
• верхний правый передний угол
• верхнее переднее ребро

Затем код будет выглядеть следующим образом:

(исполнить четыре раза) {
    собрать нижнее переднее ребро;
    повернуть весь куб на 90° вокруг вертикальной оси;
}

(исполнить четыре раза) {
    собрать нижний правый передний угол;
    повернуть весь куб на 90° вокруг вертикальной оси;
}

(исполнить четыре раза) {
    собрать переднее правое ребро;
    повернуть весь куб на 90° вокруг вертикальной оси;
}

(исполнить четыре раза) {
    собрать верхний правый передний угол;
    повернуть весь куб на 90° вокруг вертикальной оси;
}

(исполнить четыре раза) {
    собрать верхнее переднее ребро;
    повернуть весь куб на 90° вокруг вертикальной оси;
}

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

Структура данных

Грани кубика назовём стандартно: F — передняя, R — правая, B — задняя, L — левая, U — верхняя, D — нижняя. Вот стандартные вращения:


Каждое ребро имеет две прилегающих грани, каждый угол имеет три прилегающих грани. Для представления кубика я использую два массива из двенадцати (по числу рёбер) и восьми (по числу углов) целых чисел. Итак, вот массив индексов:



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

Каждое из рёбер может находиться в одном из двадцати четырёх положений, равно как и каждый угол можно поставить на двадцать четыре разных места в кубике. Вот таблица положений:



Собранный куб должен быть представлен парой массивов {0, 1, 2, 3, 8, 9, 10, 11, 20, 21, 22, 23} и {0, 1, 2, 3, 20, 21, 22, 23}, это рёбра и углы, соответственно. Например, ребро номер 4 в массиве должно иметь ориентацию 8.

Вот так выглядит представление кубика:


edges и corners — это массивы, где хранятся данные, how_edges_move и how_corners_move описывают преобразование индексов массивов edges и corners для вращения вокруг каждой из шести граней, а функция atomic_rotation() собственно и выполняет вращение одной данной грани.

Жёстко зашитые алгоритмы

Сложная часть закончилась, теперь начинатся скучная часть, открываем Cube Explorer и руками записываем некоторое количество алгоритмов для сборки.



Помните, что первым делом мы будем собирать нижнее переднее ребро? В полностью перемешанном кубике оно может находиться на любом из 24 возможных мест, поэтому массив alg_DF_edge даёт 24 разных последовательности, которые поставят ребро на место. Названия остальных массивов говорят сами за себя. Функция apply_sequence() разбивает строку на атомарные операции и вызывает atomic_rotation().

Непосредственно сборщик

Непосредственно сборщик выглядит прямым переводом псевдокода, данного в начале, на язык C++:


Обратите внимание, что rotate_entire_cube() каждый раз вызывается четыре раза, таким образом, между циклами наш куб всегда ориентирован как надо, но внутри цикла мы должны знать, как именно он ориентирован, чтобы скорректировать вывод решения на экран.

Запуск

Берём пример разобранного кубика здесь и запускаем программу:

~/MindCub3r(master)$ make && ./main RF BL UF DR UL FD DL LF RU BU BR BD FRU URB ULF LDF LUB RFD LBD RDB
g++ -Wall -Wall -Wextra -Weffc++ -pedantic -std=c++98 -c  solver.cpp -o solver.o
g++ -Wall -O3 -o ./main solver.o -lm
R1 F1 U2 R2 B1 D3 B3 D1 U1 R3 U3 R1 U3 B3 U2 B1 L1 U1 L3 L3 U2 L1 F1 U2 F3 D3 L3 U2 L1 D1 F3 U1 F1 U2 L1 U1 L3 U3 B3 U3 B1 U3 L3 U3 L1 U1 F1 U1 F3 F1 R2 F1 U3 L2 U1 F3 R2 F1 U3 L2 U1 F2 B1 L2 F3 D1 F3 D3 F2 L2 B3 U3 R2 U1 F1 B3 R2 B1 F3 U1 R2 B1 U1 B3 U3 B3 F1 R1 B1 R3 F3 

Копируем вывод в веб-валидатор и получаем:

Result is a solved cube.
Move count is 91.
Good solution!

Итак, у нас есть солвер, в следующий раз будем управлять непосредственно роботом.