Как вы представляете Rubik Cube в коде? - программирование
Подтвердить что ты не робот

Как вы представляете Rubik Cube в коде?

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

Оптимизация эшелонирования; сделать его объектно-ориентированным. Обозначение класса псевдокода, которое я использовал, это:

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

Ответ 6

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

Примечание. Это решение не запоминает ориентацию наклейки с логотипом, расположенную на белом центре.

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

Ответ 7

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

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

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

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

На самом деле вам не понадобятся 2 'последних указателя.

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

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

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

Что-то вроде этого, по крайней мере...

Ответ 8

Короткий ответ: это зависит от того, как вы собираетесь решить куб. Если ваш решатель будет использовать человеческий метод, такой как послойный подход или метод Фридриха, то основная структура данных не будет иметь большого значения. Компьютер может решить куб, используя человеческий метод, за незначительное время (намного меньше секунды) даже на самых медленных языках программирования. Но если вы собираетесь решить куб, используя более сложный вычислительный метод, такой как алгоритм с 52 шагами Thistlethwaite, алгоритм с 29 шагами Reid или алгоритм с 20 шагами Корфа, то структура данных и язык программирования имеют первостепенное значение.

Я реализовал программу Rubik Cube, которая визуализирует куб с использованием OpenGL, и в него встроены два разных типа решателей (Thistlethwaite и Korf). Решатель должен генерировать миллиарды ходов и сравнивать каждое состояние куба миллиарды раз, поэтому основная структура должна быть быстрой. Я попробовал следующие структуры:

  1. Трехмерный массив символов, 6x3x3. Цвет лица индексируется как куб [SIDE] [ROW] [COL]. Это было интуитивно понятно, но медленно.
  2. Единый массив из 54 символов. Это быстрее, чем (1), и строка и шаг вычисляются вручную (тривиально).
  3. 6 64-битных целых чисел. Этот метод, по сути, является битбордом и значительно быстрее, чем методы (1) и (2). Скручивание может быть выполнено с использованием побитовых операций, а сравнение граней может быть выполнено с использованием масок и 64-битного целочисленного сравнения.
  4. Массив угловых кубов и отдельный массив краевых кубов. Элементы каждого массива содержат индекс Куби (0-11 для ребер; 0-7 для углов) и ориентацию (0 или 1 для ребер; 0, 1 или 2 для углов). Это идеально, когда ваш решатель использует базы данных шаблонов.

Расширяя описанный выше метод (3), каждая грань куба состоит из 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 операторы 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/2.2.0 См. Model/RubiksCubeModel.{h,cpp}.

Расширяя описанный выше метод (4), некоторые из алгоритмов программного решения кубика Рубика используют итеративное углубление поиска в глубину с A *, используя базы данных шаблонов в качестве эвристики. Например, алгоритм Корфа использует три базы данных шаблонов: одна хранит индекс и ориентацию 8 угловых кубов; один хранит указатель и ориентацию 6 из 12 ребер; последний хранит индекс и ориентацию остальных 6 ребер. При использовании баз данных шаблонов быстрым подходом является сохранение куба в виде набора индексов и ориентаций.

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

0  1  2  3  4  5  6  7  8  9  10 11 // Index.
UB UR UF UL FR FL BL BR DF DL DB DR // Position (up-back, ..., down-right).
RY RG RW RB WG WB YB YG OW OB OY OG // Colors (red-yellow, ..., orange-green).

Таким образом, красно-желтый краевой кубик имеет индекс 0, а бело-зеленый краевой куб - индекс 4. Аналогично, угловые кубы могут быть проиндексированы следующим образом:

0   1   2   3   4   5   6   7
ULB URB URF ULF DLF DLB DRB DRF
RBY RGY RGW RBW OBW OBY OGY OGW

Таким образом, красно-сине-желтый угловой кубик имеет индекс 0, а оранжево-зеленый-желтый угловой кубик - индекс 6.

Ориентация каждого куба также должна быть сохранена. Кромочный элемент может быть в одной из двух ориентаций (ориентированный или перевернутый), в то время как угловой элемент может быть в трех различных ориентациях (ориентированный, повернутый один раз или повернутый дважды). Более подробную информацию об ориентации фигур можно найти здесь: http://cube.crider.co.uk/zz.php?p=eoline#eo_detection В этой модели вращение лица означает обновление индексов и ориентаций. Это представление является наиболее трудным, потому что человеку (по крайней мере, мне) трудно взглянуть на большой блок индексных и ориентировочных чисел и проверить их правильность. При этом эта модель значительно быстрее, чем динамический расчет индексов и ориентаций с использованием одной из других моделей, описанных выше, и поэтому она является лучшим выбором при использовании баз данных шаблонов. Вы можете увидеть реализацию этой модели здесь: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model (см. RubiksCubeIndexModel.{h,cpp}).

Как уже упоминалось, программа также отображает куб. Я использовал другую структуру для этой части. Я определил класс "cubie", который представляет собой шесть квадратов с 1, 2 или 3 цветными гранями для центра, ребра и угловых элементов соответственно. Кубик Рубика состоит из 26 кубиков. Грани вращаются с использованием кватернионов. Код для кубов и кубов находится здесь: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model/WorldObject

Если вы заинтересованы в моей программе решения Rubik Cube, на YouTube есть видео высокого уровня: https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be

Ответ 9

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

Ответ 10

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

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