Как бы вы представили кубик Рубика в коде?
Если бы вы разрабатывали программное обеспечение для решения кубика Рубика, как бы вы представили куб?
13 ответов
В этом документе ACM описывается несколько альтернативных способов представления кубика Рубика и сравниваются их друг с другом. К сожалению, у меня нет учетной записи, чтобы получить полный текст, но в описании говорится:
Представлены и сравнены семь альтернативных представлений кубика Рубика: массив из 3-х 3-х-3-х чисел; массив литералов размером 6 на 3 на 3; буквенная матрица 5 на 12; разреженная буквенная матрица; вектор из 54 элементов; 4-х мерный массив; и вложенный массив 3 на 3 на 3. Функции APL даны для ориентационных ходов и четвертьоборотов плюс несколько полезных инструментов для решения куба.
Кроме того, этот файл RubiksCube.java содержит довольно чистое представление вместе с соответствующим кодом для поворота разделов (если вы ищете реальный код). Он использует массив ячеек и граней.
Я реализовал программу Rubik's Cube, которая визуализирует куб с использованием OpenGL, и у него есть встроенный решатель. Решатель должен генерировать миллионы ходов и сравнивать каждое состояние куба миллионы раз, поэтому основная структура должна быть быстрой. Я попробовал следующие структуры:
- Трехмерный массив символов, 6x3x3. Цвет лица индексируется как куб [SIDE][ROW][COL]. Это было интуитивно понятно, но медленно.
- Единый массив из 54 символов. Это было улучшение скорости, и ряд и шаг были вычислены вручную (тривиально).
- 6 64-битных целых чисел. Этот метод, по сути, представляет собой битборд, и он был самым быстрым из всех.
Каждая сторона куба состоит из 9 стикеров, но центр неподвижен, поэтому нужно хранить только 8 стикеров. И есть 6 цветов, поэтому каждый цвет помещается в байте. Учитывая эти определения цвета:
enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW};
Лицо может выглядеть так, хранящееся в одном 64-разрядном целом числе:
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001
Который декодируется как:
WGR
G B
WYO
Преимущество использования этой структуры заключается в том, что rolq а также rorq побитовые операторы могут быть использованы для перемещения лица. Роллинг на 16 бит приводит к повороту на 90 градусов; прокатка на 32 бита дает поворот на 180 градусов. Соседние элементы должны храниться вручную - т.е. после вращения верхней грани, верхний слой лицевой, левой, задней и правой граней также необходимо перемещать. Поворот лица таким способом действительно быстр. Например, прокат
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001
на 16 бит дает
00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101
Расшифровывается, что выглядит так:
WGW
Y G
OBR
Другое преимущество состоит в том, что сравнение состояний куба в некоторых случаях может быть выполнено с использованием некоторых умных битовых масок и стандартных целочисленных сравнений. Это может быть довольно большим ускорением для решателя.
В любом случае, моя реализация на github: https://github.com/benbotto/rubiks-cube-cracker/tree/master/Model Смотри RubiksCubeModel.{h,cpp},
Как уже упоминалось, программа также отображает куб. Я использовал другую структуру для этой части. Я определил класс "cubie", представляющий собой квадрат с 1, 2 или 3 цветными гранями для центра, ребра и угловых элементов соответственно. Кубик Рубика состоит из 26 кубиков. Грани вращаются с использованием кватернионов. Код для кубов и кубов находится здесь: https://github.com/benbotto/rubiks-cube-cracker/tree/master/Model/WorldObject
Примечание: мой решатель не самый быстрый. Он похож на алгоритм Thistlethwaite, но моя цель состояла в том, чтобы решить куб по-человечески, а не решить его за наименьшее количество возможных ходов. Мой ответ касается базовых структур данных, а не решения куба.
Одним из способов было бы сосредоточиться на внешнем виде.
Куб имеет шесть граней, и каждая грань представляет собой массив квадратов три на три. Так
Color[][][] rubik = new Color[6][3][3];
Тогда каждый ход - это метод, который переставляет определенный набор цветных квадратов.
Оптимизация Eschew; сделать это объектно-ориентированным. Схема класса псевдокода, которую я использовал:
class Square
+ name : string
+ accronym : string
class Row
+ left_square : square
+ center_square : square
+ right_square : square
class Face
+ top_row : list of 3 square
+ center_row : list of 3 square
+ bottom_row : list of 3 square
+ rotate(counter_clockwise : boolean) : nothing
class Cube
+ back_face : face
+ left_face : face
+ top_face : face
+ right_face : face
+ front_face : face
+ bottom_face : face
- rotate_face(cube_face : face, counter_clockwise : boolean) : nothing
Объем используемой памяти настолько мал, а обработка настолько минимальна, что оптимизация совершенно не нужна, особенно когда вы жертвуете удобством использования кода.
Интересный способ представления куба используется программным обеспечением "Cube Explorer". Используя много умных математик, этот метод может представлять куб, используя только 5 целых чисел. Автор объясняет математику своей программы на своем сайте. По мнению автора, представление подходит для реализации быстрых решателей.
Есть много способов сделать это. Некоторые способы более эффективно используют память, чем другие.
Я видел, как люди используют массив 3 x 3 x 3 кубоидных объектов, где кубоидный объект должен хранить информацию о цвете (и да, этот центральный объект никогда не используется). Я видел, как люди используют 6 массивов, каждый из которых представляет собой массив кубов 3 х 3. Я видел массив кубоидов 3 x 18. Есть много возможностей.
Вероятно, большее беспокойство вызывает то, как представить различные преобразования. Поворот одной грани физического куба (все движения куба - это, по сути, вращения одной грани) должен был бы отображаться путем обмена множеством кубоидных объектов.
Ваш выбор должен иметь смысл для любого приложения, которое вы пишете. Может быть, вы только рендеринг куба. Может быть, что нет интерфейса. Возможно, вы решаете куб.
Я бы выбрал массив 3х18.
Есть 20 кубиков, которые имеют значение. Так что один из способов сделать это - это массив из 20 строк. Строки будут содержать 2 или 3 символа, обозначающие цвета. Любой отдельный ход затрагивает 7 кубиков. Так что вам просто нужен реппер для каждой из шести сторон.
Примечание. В этом решении не удается запомнить ориентацию наклейки с логотипом, которая находится в белом центре.
Кстати, я однажды помог кому-то сделать программный кубик Рубика, может быть, 15 лет назад, но я не могу вспомнить, как мы его представляли.
Вы можете представить куб в виде трех вертикальных круглых связанных списков, которые пересекаются с тремя горизонтальными связанными списками.
Всякий раз, когда вращается определенный ряд куба, вы просто поворачиваете соответствующие указатели.
Это будет выглядеть так:
struct cubeLinkedListNode {
cubedLinkedListNode* nextVertical;
cubedLinkedListNode* lastVertical;
cubedLinkedListNode* nextHorizontal;
cubedLinkedListNode* lastHorizontal;
enum color;
}
Возможно, вам на самом деле не нужны 2 последних указателя.
[Я сделал это с C, но это можно сделать на Java или C#, просто используя простой класс для cubeLinkedListNode, где каждый класс содержит ссылки на другие узлы. ]
Помните, что существует шесть взаимосвязанных круглых связанных списков. 3 вертикальных 3 горизонтальных.
Для каждого поворота вы просто просматриваете соответствующий круговой связанный список, последовательно сдвигая связи вращающегося круга, а также соединительные круги.
Нечто подобное, по крайней мере...
Самое короткое представление выглядит примерно так: https://codepen.io/Omelyan/pen/BKmedK
Куб разворачивается в одномерный массив (вектор из 54 элементов). Функция вращения в несколько строк меняет местами стикеры и основывается на симметрии куба. Вот полная рабочая модель на C, которую я сделал в 2007 году, когда был студентом:
const byte // symmetry
M[] = {2,4,3,5},
I[] = {2,0,4,6};
byte cube[55]; // 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1, ... need to be filled first
#define m9(f, m) (m6(f, m)*9)
byte m6(byte f, byte m) {return ((f&~1)+M[m+(f&1)*(3-2*m)])%6;}
void swap(byte a, byte b, byte n) {
while (n--) {byte t=cube[a+n]; cube[a+n]=cube[b+n]; cube[b+n]=t;}
}
void rotate(byte f, byte a) { // where f is face, and a is number of 90 degree turns
int c=m9(f, 3), i;
swap(c, c+8, 1);
while (a--%4) for (i=2; i>=0; --i)
swap(m9(f, i) + I[i], m9(f, i+1) + I[i+1], 3),
swap(f*9+i*2, f*9+i*2+2, 2);
swap(c, c+8, 1);
}
Кубик Рубика имеет:
- 8 углов, каждый из которых содержит уникальный угловой кублет.
- 12 ребер, каждое из которых содержит уникальный реберный кублет.
- 6 центров, каждый из которых содержит уникальный центральный кублет.
Каждый угловой кублет может быть в одной из 3 ориентаций:
- не вращается;
- повернут по часовой стрелке на 120°; или
- повернут против часовой стрелки на 120°.
Каждый реберный кублет может быть в одной из двух ориентаций:
- не перевернутый; или
- перевернулся на 180°.
Центральные кубики закреплены друг относительно друга; однако существует 24 возможных ориентации (игнорируя вращение отдельных центров, что имеет значение только в том случае, если вы собираете куб с картинками), поскольку есть 6 способов выбрать центральный кублет, который находится на «верхней» грани куба, а затем 4 способа выбрать центральный кублет, который будет на «передней» грани.
Вы можете сохранить это как:
- массив из восьми 3-битных целых чисел, каждое из которых представляет угловой кубик в угловой позиции.
- массив из восьми 2-битных целых чисел, каждое из которых представляет ориентацию углового кубика в угловой позиции.
- массив из двенадцати 4-битных целых чисел, каждое из которых представляет реберный кублет в позиции ребра.
- массив из двенадцати 1-битных целых чисел, каждое из которых представляет ориентацию реберного кублета и позицию ребра.
- 5-битное целое число, представляющее перечисление всех 24 возможных ориентаций центральных кубиков.
Это дает в общей сложности 105 бит (14 байт).
Оптимизация пространства:
Поскольку углы всегда зафиксированы, можно предположить, что они никогда не двигаются и их не нужно хранить. При этом, если вы хотите сделать
Eдвигаться, затем сделать эквивалентU D'пара ходов вместо этого.Это уменьшит размер до 100 бит (13 байт).
Если вы ограничиваете представление разрешимыми кубами, то можно хранить куб в меньшем пространстве как:
- Как только вы узнаете 7 угловых кубиков, вы сможете понять, что такое 8-й кубик.
- Ориентация угловых кубиков имеет фиксированную четность, поэтому, как только вы узнаете ориентацию 7 углов, вы можете получить 8-й.
- Аналогично для ребер, вам нужно только сохранить 11 из 12 кублетов ребер и ориентации ребер, и вы можете вычислить оставшийся.
Это экономит еще 10 бит, что в сумме дает 90 бит (12 байт). Однако расчеты, необходимые для обработки недостающей информации, могут означать, что эта оптимизация пространства не стоит снижения производительности.
Больше оптимизации пространства:
Если вы действительно хотите оптимизировать пространство для куба, то:
- 8 угловых кубиков можно расположить в
8! = 40320перестановки и40320может быть представлен в16биты. - 7 троичных (с основанием 3) цифр могут представлять ориентацию углов (определяя положение 8-го числа) и
3^7 = 2187и может быть представлен в12биты. - 12 краевых кубиков можно расположить в
12! = 479001600перестановки и479001600может быть представлен в29биты. - 11 двоичных цифр могут представлять ориентацию ребер (определяя позицию 12-го числа), которая была бы
11биты.
Это дает в общей сложности 68 бит (9 байт).
Максимальное количество перестановок собираемого кубика Рубика равно(8!*3^8*12!*2^12)/12 = 43,252,003,274,489,856,000 ~= 4.3*10^19которые можно хранить в66бит (9 байт), и хотя можно перечислить все возможные решения, не стоит сохранять эти последние 2 бита.
Как перестановка из 48 граней, которые могут двигаться. Основные вращения также являются перестановками, и перестановки могут быть составлены, они образуют группу.
В программе такая перестановка будет представлена массивом из 48 элементов, содержащих числа от 0 до 47. Цвета, соответствующие числам, являются фиксированными, поэтому визуальное представление может быть вычислено из перестановки, и наоборот.
Другие хорошо рассмотрены, описывая физический куб, но касаясь состояния куба... Я бы попытался использовать массив векторных преобразований для описания изменений куба. Таким образом, вы можете сохранить историю кубика Рубика по мере внесения изменений. И мне интересно, если бы вы могли умножить векторы в матрицу преобразования, чтобы найти самое простое решение?
Я нашел очень полезным хранить состояние как сопоставление координат центра кублета за пределами грани с цветом. Так, например, верхняя грань переднего верхнего правого кубика
state[1, -1, 2]. Таким образом, перемещения выполняются путем простого применения поворотов к индексам.
Вы можете увидеть простой симулятор, который я написал здесь: https://github.com/noamraph/cube .