Кубик Рубика

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

Доказано, что число всех достижимых различных состояний традиционного 6-цветного кубика Рубика 3×3×3 равно 43 252 003 274 489 856 000, а оптимальная последовательность ходов, необходимых для сборки кубика Рубика из любого состояния не превышает 20. Алгоритм, собирающий кубик Рубика за минимальное число ходов, традиционно называется «алгоритмом Бога», а 20 – числом Бога.

Рассмотрим более простую модель кубика Рубика 2×2×2, в которой используется всего 3 цвета: красный (R), синий (B) и зеленый (G). При этом противоположные грани окрашены в одинаковый цвет. Под ходом будем понимать вращение одной из граней на угол 90º. Поскольку всего 6 граней (передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)), то всего может быть 12 различных ходов (по часовой и против часовой стрелки для каждой грани). Ходы обозначаются буквами соответствующих граней, если ход происходит против часовой стрелки, то после буквы ставится апостроф (ASCII 39).

По заданной конфигурации трехцветного кубика Рубика 2×2×2 требуется найти оптимальный алгоритм (алгоритм Бога), решающий головоломку.

Входные данные

Входной файл INPUT.TXT содержит две строки, определяющие конфигурацию кубика Рубика. Первая строка содержит информацию о цветах верхнего слоя для каждой грани – пары символов, разделенные пробелом. Вторая строка аналогичным образом описывает нижние слои. Порядок граней (слева направо): передняя, левая, задняя, правая, верхняя, нижняя.

Выходные данные

В выходной файл OUTPUT.TXT выведите оптимальное решение головоломки для заданной конфигурации кубика Рубика. Если решений несколько, выведите любое. Если задана начальная конфигурация (кубик Рубика собран), то следует вывести «Solved».

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]