Теория множеств и кубик Рубика

[Doob 2 749]

Подскажите, как можно записать алгоритм вращения сторон кубика Рубика, используя теорию множеств.

 

У кубика есть два типа множеств - квадратов и действий, вот список:

• Квадраты

1. угловой (24 шт)
2. боковой (24 шт)
3. центральный (6 шт)

• Действия (для одной стороны)

1. сдвиг верхнего слоя
2. сдвиг центрального слоя
3. сдвиг нижнего слоя
4. вращение активной стороны

Для четырех сторон, лежащих в одной плоскости, первые три действия не отличаются.

Так как у нас 3 таких группы по 4 стороны, количество действий = 9  (3 группы*3 слоя, инверсию не считаем)

 

Вопрос:

Как должен выглядеть оптимальный алгоритм вращения?

 

Изначально я записал правила в таблицу и по этим правилам переназначал цвета в таблице состояний кубика просто сдвигая параметр квадрата по петле.

Правила были примерно такие: {1,4,7}, {2,5,8}, {3,6,9}, {1,2,3,6,9,8,7}

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

[Krutoy 1 169]

Если кубик хранить в виде 3х массивов (срез по высоте), то вращение в одну сторону можно было бы сделать вставлением конца в начало:

-- Наш массив первого среза кубика
local s = {[0] = с, с, [...], с}

-- Берем последние 2 числа из массива
-- и вставляем их в начало. Все остальные индексы переписываются
for i=1,2 do
  table.insert(s, 1, table.remove(s))
end

Аналогично можно сделать и вращение в другую сторону, удаляя элементы с начала и вставляя их в конец.

 

А вот с вращением боковых сторон нужно делать по правилам как ты и написал. Но при этом можно использовать функцию что я указал выше.

Например, передняя сторона куба записанна как:

{{1,c},{1,c},{1,c},{2,c},{2,c},{2,c},{3,c},{3,c}}

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

{{1,c},{2,c},{3,c},{3,c},{3,c},{2,c},{1,c},{1,c}}

И соответственно по индексам мы назначаем цвета в новую таблицу после поворота.

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

 

 

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

Изменено 19 апреля, 2015 пользователем Krutoy

[Doob Автор темы 2 749]

Ну я так и делал, все это очевидно, но расширять придется вручную.

Хотелось бы найти более математическое решение, т. е. чтобы можно было запросить у программы кубик 3х3х3 или 90х90х90, а она из базового алгоритма берет все сдвиги в вращения (которых всего 2 штуки) и применяет для каждого среза.

 

А гуглить я пробовал, запрашивать "кубик Рубика" и "алгоритм" бесполезно - только алгоритмы сборки или "физические" реализации (эмулируются срезы и вращение 3д модели), а более абстрактные также не расширяются.

 

Вот мой нубокод: http://pastebin.com/XFxXRKUu, с правилами в таблице будет короче, но принцип точно такой же.

[Krutoy 1 169]

Вот мой нубокод: http://pastebin.com/XFxXRKUu, с правилами в таблице будет короче, но принцип точно такой же.

Да, действительно китайский код =)

[Doob Автор темы 2 749]

Итак, что мы имеем?
 
1. Срезы в виде одномерного массива, сдвиг таблицы петлей (индекс +- длина грани)
Можно автоматизировать генерацию срезов для любой длинны грани, но получается очень избыточно (но какая разница, если допиливать не надо?).
Если сделать срез в виде двумерного массива, то правила сдвига усложняются, но упрощается вывод относительных координат на командный блок.
 
2. Сканирование  сторон в срезе и круговое переназначение координат (по тому-же принципу, по которому происходит построение кругов отражением 1/8 круга).
Так как у меня используются относительные координаты, координаты командного блока = x0 y0 z0, берем срез.
####[-2][-1][00][+1][+2][xx]
[+2][00][RR][RR][RR][00]
[+1][GG][00][00][00][BB]
[00][GG][00][00][00][BB]
[-1][GG][00][00][00][BB]
[-2][00][YY][YY][YY][00]
[yy]
Присваиваем [x, y = y, x] и (если я ничего не путаю) получаем срез повернутый на 90 градусов.
 
Подкиньте еще идеи с реализацией.
Кстати, вот TouchCube интересно бы узнать, что внутри.

[Doob Автор темы 2 749]

Мда... Получается отражение по диагонали.

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

 

Вот какие правила можно вывести:

угол = [-x, -y]=>[-x, +y]=>[+x, +y]=>[+x, -y]=>[-x, -y]

центр = [-x, 0y]=>[0x, +y]=>[+x, 0y]=>[0x, -y]=>[-x, 0y]

 

берем срез кубика 3x3, у него кроме центрального еще два кубика с такими правилами:

x-1, y+2 => x+2, y+1 => x+1, y-2 => x-2, y-1 => x-1, y+2
x+1, y+2 => x+2, y-1 => x-1, y-2 => x-2, y+1 => x+1, y+2
[+-]____________[+-]___[+-]_____________[+-]___[+-] - это у нас инверсия знака

 

Далее у нас заметна последовательность типа:

x-3, y+4 => x+4, y+3 => x+3, y-4 => x-4, y-3 => x-3, y+4
x-2, y+4 => x+4, y+2 => x+2, x-4 => x-4, y-2 => x-2, y+4
x-1, y+4 => x+4, y+1 => x+1, y-4 => x-4, y-1 => x-1, y+4

и это только для 1/8 периметра, т. е. вращается только половина квадрата, надо еще добавить инверсию знака как я указал для 3х3

 

в итоге выходит цикл с такой формулой:

 

от i+v до i+1
  x = 0-m, y = i-1 =>
  x = i-1, y = m  =>
  x = 0-m, y = 0-(i-1) =>
  x = 0-(i-1), y = m =>
  x = 0-m, y = i-1

 

v = длина грани
m = значение сконвертированное из длинны грани по формуле
3 = 1
5 = 2
7 = 3
9 = 4
11 = 5

...

 

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

Изменено 24 апреля, 2015 пользователем Doob

[Krutoy 1 169]

Я уже если честно начал путаться. Задача сложная математически, и мне не хватает ума что бы помочь тебе.