Как бы вы представили кубик Рубика в коде?

Question

Если бы вы разрабатывали программное обеспечение для решения кубика Рубика, как бы вы представили куб?

Answer 1

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

Представлены и сравнены семь альтернативных представлений Кубика Рубика: массив из 3-х 3-х-3-х чисел; массив литералов размером 6 на 3 на 3; буквенная матрица 5 на 12; разреженная буквенная матрица; вектор из 54 элементов; 4-х мерный массив; и вложенный массив размером 3 на 3 на 3. Функции APL даны для ориентационных ходов и четвертьоборотов плюс несколько полезных инструментов для решения куба.

Кроме того, этот RubiksCube.java файл содержит довольно чистое представление вместе с соответствующим кодом для вращения секций (если вы ищете реальный код). Он использует массив ячеек и граней.

Answer 2

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

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

Answer 3

Одним из способов было бы сосредоточиться на внешнем виде.

Куб имеет шесть граней, и каждая грань представляет собой массив квадратов три на три. Так

Color[][][] rubik = new Color[6][3][3];

Тогда каждый ход - это метод, который переставляет определенный набор цветных квадратов.

Answer 4

Интересный способ представления куба используется программным обеспечением "Cube Explorer". Используя много умных математик, этот метод может представлять куб, используя только 5 целых чисел. Автор объясняет математику своей программы на своем сайте . По мнению автора, представление подходит для реализации быстрых решателей.

Answer 5

Есть 20 кубиков, которые имеют значение. Так что один из способов сделать это - это массив из 20 строк. Строки будут содержать 2 или 3 символа, обозначающие цвета. Любой отдельный ход затрагивает 7 кубиков. Так что вам просто нужен реппер для каждой из шести сторон.

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

Кстати, я однажды помог кому-то сделать программный кубик Рубика, может быть, 15 лет назад, но я не могу вспомнить, как мы его представляли.

Answer 6

Есть много способов сделать это. Некоторые способы более эффективно используют память, чем другие.

Я видел, как люди используют массив кубических объектов 3 x 3 x 3, где кубический объект должен хранить информацию о цвете (и да, этот центральный объект никогда не используется). Я видел, как люди используют 6 массивов, каждый из которых представляет собой массив кубов 3 х 3. Я видел массив кубоидов размером 3 x 18. Есть много возможностей.

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

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

Я бы выбрал массив 3х18.

Answer 7

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

Всякий раз, когда вращается определенный ряд куба, вы просто поворачиваете соответствующие указатели.

Это будет выглядеть так:

struct cubeLinkedListNode {
    cubedLinkedListNode* nextVertical;
    cubedLinkedListNode* lastVertical;
    cubedLinkedListNode* nextHorizontal;
    cubedLinkedListNode* lastHorizontal;
    enum color;
}

Возможно, вам не нужны два последних указателя.

[Я сделал это с C, но это можно сделать на Java или C #, просто используя простой класс для cubeLinkedListNode, где каждый класс содержит ссылки на другие узлы. ]

Помните, что существует шесть взаимосвязанных круглых связанных списков. 3 вертикальных 3 горизонтальных.

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

Нечто подобное, по крайней мере ...

Answer 8

Я реализовал программу 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, но моей целью было решить куб по-человечески, а не решить его за наименьшее количество возможных ходов. Мой ответ касается базовых структур данных, а не решения куба.

Answer 9

Как перестановка из 48 граней, которые могут двигаться. Основные вращения также являются перестановками, и перестановки могут быть составлены, они образуют группу.

В программе такая перестановка будет представлена ​​массивом из 48 элементов, содержащих числа от 0 до 47. Цвета, соответствующие числам, являются фиксированными, поэтому визуальное представление может быть вычислено из перестановки и наоборот.

Answer 10

Остальные хорошо рассмотрены, описывая физический куб, но относительно состояния куба ... Я попытался бы использовать массив векторных преобразований для описания изменений куба. Таким образом, вы можете сохранить историю кубика Рубика, когда будут внесены изменения. И мне интересно, если бы вы могли умножить векторы в матрицу преобразования, чтобы найти самое простое решение?