Алгоритм расположения наклеек на кубике Рубика произвольного размера

Допустим есть кубик рубика произвольного размера NxNxN.
На входе имеем начальное положение блока A(Xa, Ya, Za), конечное положение B(Xb, Yb, Zb) и углы вращения вокруг трёх осей, на которые блок повернулся в процессе перемещения... Траектория перемещения может быть очень запутанной и нам не интересна. Эти входные данные абсолютно однозначно определяют конечное состояние одного из блоков (положение и разворот). Пытаюсь вывести алгоритм который по входным данным возвратит куда переместилась наклейка на данном блоке.
Рассмотрим пример по картинке:
Цифрой 1 обозначим начальное положение блока A(0, 2, 2). Цифрой 2 - конечное положение блока B(2, 2, 0). Для лучшего понимания можно добавить что второе положение из первого в данном случае мы получили прокрутив: (R U R') (описание снизу) Потому имеем повороты вокруг трёх осей R(-90, 90, 0) (т.е. при повороте R блок 1 не менял положения, при U повернулся вокруг Y по часовой, при R' - вокруг X против часовой).
На выходе нужно вычислить, что если белая наклейка в исходном положении была сверху, то в конечном стала спереди, соответственно оранжевая была слева, стала сверху, а синяя была сзади, стала справа
Важно что какие были повороты мы не знаем, на входе их нет, а к конечной позиции можно прийти другим путём и иметь другие повороты, хотя внешне ничего не изменится (другие блоки будут на других местах, но они нам не интересны), потому как их задействовать в алгоритме пока не ясно, но они необходимы! Т.е. при цепочке, например (L F) мы окажемся в том же положении, так же развёрнуты, но развороты будут на входе R(90, 0, 90), а при цепочке (L2 D R) тоже достигнем нужного положенияи разворота, но развороты будут R(90, -90, 0).
Необходим свежий взгляд со стороны, что-то я немного подзавис!
PS:
Классическая запись вращений: Up, Down, Left, Right, Front, Back начальные буквы названий сторон для поворота по часовой стрелке (если она находится перед нами) и с апострофом, например R' для поворота против часовой стрелки, а так же с 2, например R2 для поворота на 180 градусов. Классическое расположение цветов: F - зеленый, U - белый, B - синий, R - красный, L - оранжевый, D - жёлтый. Работа ведётся с двухмерной разметкой кубика.

Информация к размышлению: только мне кажется, что тут какая-то логическая ошибка? Рассмотрим несколько простых примеров(в каждом примере следим за передним-правым-верхним углом):
Прокручиваем F2 L2 Имеем вектор разворота R(180, 0, 180), По оси Y он не поворачивался, но если бы мы не знали как он был туда поставлен, могли бы с уверенностью сказать поворотом вокруг Y на 180! Прокручиваем R B L F Наблюдаемый кубик возвращается в исходное положение, т.е. разница векторов координат (0, 0, 0), развороты вокруг осей сокращаются и тоже получаем R(0, 0, 0). Т.е. вообще никакой информации, но кубик развёрнут по часовой стрелке! Прокручиваем F' L' B' R' Наблюдаемый кубик возвращается в исходное положение, т.е. разница векторов координат (0, 0, 0), развороты вокруг осей так же сокращаются и тоже получаем R(0, 0, 0). Т.е. снова вообще никакой информации, но кубик развёрнут уже против часовой стрелки!

Ответ

Давайте попробуем составить алгоритм. Я предлагаю алгоритм — поиск в ширину.
Определим обьект кубика. У куба 6 сторон. 6 цветов. Каждая сторона — 9 элементов. Давайте куб опишем массивом на 54 (6 × 9 = 54) элемента. Тогда конечная цель — чтобы каждые 9 элементов были равны. Давайте "нарисуем" модель.
18 19 20 21 22 23 24 25 26 0 1 2 9 10 11 36 37 38 45 46 47 3 4 5 12 13 14 39 40 41 48 49 50 6 7 8 15 16 17 42 43 44 51 52 53 27 28 29 30 31 32 33 34 35 Давайте определим действия, которые можно делать с кубиком. И так, у нас есть 6 граней, каждую сторону можно вращать вокруг собственной оси в обе стороны. Итого, у нас есть 6 × 2 = 12 действий. Нужно описать все 12 действий. Я опишу вам одно, остальные — самостоятельно. Для описания — элементы будут меняться местами. Для наглядности — давайте вращать грань 9-17 вокруг себя, тогда я парами указываю элементы, которые поменяются местами:
18 19 20 21 22 23 24-36 25-39 26-42 0 1 2-26 9-11 10-14 11-17 36-29 37 38 45 46 47 3 4 5-25 12-10 13 14-16 39-28 40 41 48 49 50 6 7 8-24 15-9 16-12 17-15 42-27 43 44 51 52 53 27-2 28-5 29-8 30 31 32 33 34 35
В виде пар это будет вид
24-36,25-39,26-42, 2-26, 9-11,10-14,11-17,36-29,5-25, 12-10, 14-16,39-28, 8-24, 15-9,16-12,17-15,42-27,27-2 ,28-5, 29-8
Вышло 20-ть пар. 12 + 8 = 20. Если пары поменять местами — будет вращение в противоположную сторону. Таких пар по 20 штук должно быть 12 вариантов. Я показываю один.
Попробую описать вращение рисунков в 3D. Вращение будет происходить только для 9 элементов, с 9-того по 17 включая 13. Остальные вращаться не будут, если это 2D проекция, а уже переводя это в 3D проекцию, получим больше вариантов.
Упакованый вариант разворота a[i] = (a[i] & 7) + ((a[i] + 8) & (8+16)) и влево a[i] = (a[i] & 7) + ((a[i] - 8) & (24)) применить это для 9 елементов после перестановок. Тогда (a[i] & 24) = {0,8,16,24} в зависимости от разворота.
Вариант разворота простой с and x.size = (x.side+1)&3 или x.size = (x.side-1)&3
Вариант разворота усложнённый if (x.size=3) x.size = 0; else x.size++ или if (x.size=0) x.size = 3; else x.size--
UPD Важно: при операции вращения, лучше создавать отдельный массив, поскольку можно "случайно" присвоить два раза одну ячейку. Например при в 11 мы присвоили 9, а в 17 присваиваем 11 — и получаем "сбой", поэтому слева от присваивания должен быть исходный массив, а справа (куда приваиваем) — дубликат исходного массива.
ИТОГ: делаем 20 операций перестановки, потом 9-операций 2D вращения, при этом один из 9 — центральный элемент, который не вошёл в 20.
Имея обьект кубика, давайте определим конечное условие: это будет о[0]=o[1]=…=o[8], о[9]=o[10]=…=o[17], …, т.е. все каждые 9 элементов массива должны быть равны. Теперь, когда у нас есть "обьект", то мы создаём массив обьектов, и начинаем строить дерево. Каждый новый уровень, добавляет по несколько элементов в массив. Нужно это для того, чтоб убрать "лишнии" движения, и найти решение используя поиск в ширину.
Делаем структуру (№итерации, №действия(1-12), №элемента, который привёл к появлению даного, "обьект"(массив на 54)) Далее строим 1-вую итерацию, т.е. цикл на 12 перестановок граней, получаем
a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj), a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj);
Каждый обьект, проверяем условие [3]. Делаем 2-рую итерацию. Тут уже возникнет проблема. Начнут появляться дубли. Дубли образуются тогда, когда мы одну и ту же грань вращаем сначала влево, а потом на 2-й итерации, её же вправо. Можно придумать как алгоритмически этого избежать, но сложно. Кроме того, нужно ещё фильтровать 4-х кратное вращение и т.д., поэтому проще — просто фильтровать дубли. Т.е, как по мне — то проще — проверять с добавлением нового элемента массива — нет ли дублей ниже, в элементах a[0]…a[n] (a[12]). Вторая итерация принесёт 12 × 12 = 144 элемента, но половина — будут точно дубли. Поэтому будет где-то +72 элемента. Для упрощения сделаем так. Второй уровень будет иметь примерно такой вид
a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj), a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj); a[13]=(2,1,1,obj),a[14]=(2,1,2,obj)...a[84]=(2,12,6,obj)
За тем повторяем итерации, до тех пор, пока решение не будет найдено (т.е. условие [3] не будет выполнено. По массиву можно будет установить ход событий (т.е. если ответ 84, то 84 породил элемент 6, который породил элемент 0. в элементе 6, указано куда вращали).

P.S. При 3D рендеринге, будет 6 × 4 = 24 положения рисунка. Если рендеринг будет плавным, то нужно будет из одного из 24 положений плавно переходить к другому. Квадрат можно наклеить на куб 4-мя вариантами.
У куба 6 сторон, поэтому для 3D — у вас 24 вариата. Но если оперировать 24-мя вариантами, то задача вращения усложняется, т.к. прийдётся вращать все 20-ть элементов (20 пар из [2]). Проще вращать 9-елементов 4-мя комбинациями, а +6 комбинаций добавить на фазе рендеринга в 3Д (6- в зависимости на какой стороне куба мы оказались). Т.е. при рендеринге будет realside = side+ kubeside* 4 где size — значение одного из 54 елементов, size в пределах [0..3], а kubeside в пределах [0..5] — означает на какой стороне куба мы находимся. После проецирование на 2D проскость, может оказаться что эти 24 варианта перешли в 12 или меньше, но именно цифра 24 дает основу, которая "убирает" хаос. Т.е. задаёт порядок такой, что грань не может быть развёрнута "не туда".
Мне показалось что про 24 комбинации не совсем понятно. Попробую нарисовать
^ ^ ^ < ^ v > > > < ^ > ^ ^ > ^ ^ ^ > > > < v > v v > ^ < < < ^ v < v > ^ ^ v < < < v v v < < > ^ ^ > V V V
это комбинация из 4-х положений на двухмерке. Она домножится на 6 вариантов, потому что кажую из 6 сторон, прийдётся рендерить на 3D 6-ю способами. А 3D модель будет… надо подумать в чём можно быстро нарисовать… Имеется ввиду что комбинация 0..53 × 4 варианта развотота × 6 вариантов нахожнения на стороне дадут всегда однозначно 3D-вектор. 0..53 даст однозначно 3D координату вектора, а 24 (4 × 6) даёт разворот, направление вектора трехмерное. Т.е. можно составить массив на 54 координаты, и на 24 вектора направлености — и 3D преобразование гладко пройдет.
Расписываю 24. В 2D у нас будет 4-ре плоских вектора: 0, 90, 180, 270 (поворот в плоскости XY).
В 3Д наложатся такие повороты (XY, XZ, YZ).
^y 2 (0,0,90) 0(0,270,0) 1 (0,0,0) 4(0,90,0) 5(0,0,180) 3 (0,0,270) --x>
Надеюсь, я правильно вектора поворота в градусах расписал. Добавив (0, 90, 180, 270) в первую координату вращения XY — получим 24 комбинации разворота.
5-тый (спинка) — спорный, если его развернуть на 180 по XZ и ещёраз на 180 по YZ — то мы получим "исходное положение обьекта" в почти "зеркальном виде". 5(0,180,0) Не могу сказать, как правильно 5(0,180,0) или так 5(0,180,180) или так 5(0,0,180)

Ускорение. Так как кубик безсмысленно крутить одну сторону влево-вправо и т.п., можно добаить в цикл на 12 условия запрещающие это делать. Например, так
if (level >= 2) /*then*/ { if (( a[a[i].prev].turn & 14 ) == (turn & 14)) /*then*/{ // Если предыдущую грань двигали ту же самую if (a[a[i].prev].turn != turn ) /*then*/ continue; //Если Если предыдущую грань двигали в другую сторону // то не рассматриваем дальше, убрать туда-сюда движение // сюда код прийдёт, если более одного раза двигаем одну грань if (a[a[a[i].prev].prev].turn == turn) continue; // Запрет поворачивать третий раз куб в одну сторону }
Т.е. в итоге алгоритм будет такой.
Задаём начальное условие Начало итераций, цикл на 12 движений Проверяем условия на лишние движения, если такие есть — переходим на 2. Выполняем движение, готовим a` Проверяем "граничное условие" что кубик "собран". Если собран — решение найдено. Проверяем что а' отсутствует в массиве а. Если присутствует — к п 2. добавляем а' в массив, и переходим к 2. По завершению цикла создаём ещё одну итерацию.
Почитав про кубик-рубика в википедии, я нашел запись, что за 20 ходов можно найти решение. Возможно, более эффективным будет поиск вглубину с ограничением на 20. Для такого поиска нужен будет массив на 20, а не на несколько тысяч, как в этом варианте.