Если я пытаюсь смоделировать кубик Рубика , как бы вы создали структуру данных для хранения состояния куба в памяти, с X числом плиток на стороне?
Что нужно учитывать:
- куб может быть любого размера
- это кубик Рубика, поэтому слои можно вращать
Если я пытаюсь смоделировать кубик Рубика , как бы вы создали структуру данных для хранения состояния куба в памяти, с X числом плиток на стороне?
Что нужно учитывать:
Ответы:
Что не так с простым старым массивом размера
[6X][X]
? Вам не нужно знать о внутренних мини-кубах, потому что вы их не видите; они не являются частью состояния куба. Скройте два уродливых метода за красивым и простым в использовании интерфейсом, протестируйте его до смерти и вуаля, все готово!источник
As long as you know how the six surfaces are "threaded" together
Именно это даст вам более надежная структура данных. Я думаю, что мы спорим об одном и том же. Стороны массива, а сторона - это массив блоков, однако есть много интересных свойств относительно сторон и блоков, которые помогают понять, что «многопоточность» Этот термин не очень нравится, потому что его можно спутать с многопоточностью; )Следует отметить, что я страстный любитель скорости, но я никогда не пытался программно представлять кубик Рубика в алгоритме или структуре данных.
Вероятно, я бы создал отдельные структуры данных для захвата уникальных аспектов каждого блока в кубе.
В кубе есть 3 различных типа блоков:
Угловой блок - у него есть три цветных грани и три смежные части, с которыми он будет разделять сторону в любое время.
Edge Block - имеет две цветные грани и имеет 4 смежных фигуры, с которыми у него будет общая сторона в любое время. В блоках 3х3 всегда 2 центральных и 2 угловых.
Центральный блок - в кубе 3х3 эта часть не подвижна, однако ее можно вращать. У него всегда будет 4 смежных краевых блока. В больших кубах есть несколько центральных блоков, которые могут делиться с другим центральным блоком или краевой частью. Центральные блоки никогда не примыкают к угловому блоку.
Зная это, у Блока может быть список ссылок на другие блоки, к которым он прикасается. Я бы сохранил другой список списков, который был бы списком блоков, представляющих одну грань куба, и списком, в котором хранятся ссылки на каждую грань куба.
Каждое лицо куба будет представлено как уникальное лицо.
С этими структурами данных было бы довольно легко написать алгоритм, который выполняет преобразование вращения на каждой грани, перемещая соответствующие блоки в соответствующие списки и из них.
РЕДАКТИРОВАТЬ: Важное примечание, эти списки должны быть заказаны, конечно, но я забыл упомянуть об этом. Например, если я переверну правую сторону, то левый угловой блок правой стороны переместится в правый угол правой стороны и повернется по часовой стрелке.
источник
list of lists
. может быть, лучше просто иметь неупорядоченный список блоков, которые вы можете запросить. и вы просто обновляете ссылки на соседние блоки при выполнении преобразования. Если вы хотите получить список всех блоков на грани, вы можете запросить список всех смежных блоков в центральном блоке (ах), верно?Когда я думаю об этой проблеме, я думаю о статическом кубе с цветами, движущимися по нему известными узорами. Так....
Объект Cube содержит 6 объектов Side, которые остаются фиксированными с индексами 0-5. Каждая сторона содержит 9 объектов позиции, которые остаются фиксированными с индексами 0-8. Каждая позиция содержит цвет.
Для простоты обрабатывайте каждое действие с шагом в четверть оборота. Есть 3 оси вращения, каждая в 2 возможных направлениях, всего 6 возможных действий на кубе. С этой информацией становится довольно простой задачей наметить 6 возможных действий на кубе.
Таким образом, зеленый цвет на стороне 6, позиции 3, может перемещаться в сторону 1, позицию 3 или сторону 2, позицию 7, среди прочего, в зависимости от предпринятых действий. Я недостаточно изучил это, чтобы найти какие-либо математические переводы, но, вероятно, появятся шаблоны, которые вы можете использовать в коде.
Для этого никогда не начинайте со случайного состояния куба. Вместо этого начните с решенного состояния и программно выполните n действий, чтобы перевести куб в случайное начальное состояние. Поскольку вы только предприняли законные действия, чтобы добраться до текущего состояния, куб должен быть разрешимым.
источник
Я обнаружил, что система координат XYZ - это простой способ обращения к кубу Рубика, а матрицы вращения - простой, общий способ реализации вращений.
Я создал класс Piece, содержащий вектор позиции
(x, y, z)
. Кусок можно вращать, применяя к его положению матрицу вращения (умножение матрицы на вектор). Пьеса также отслеживает цвета в кортеже(cx, cy, cz)
, давая цвета, обращенные вдоль каждой оси. Небольшое количество логики обеспечивает правильное обновление этих цветов во время поворота: поворот на 90 градусов в плоскости XY означает, что мы должны поменять местами значенияcx
иcy
.Поскольку вся логика вращения инкапсулирована в классе Piece, Cube может хранить неупорядоченный список Pieces, и вращения могут выполняться в общем виде. Чтобы сделать поворот левой грани, выберите все фигуры с координатой х -1 и примените соответствующую матрицу вращения к каждой фигуре. Чтобы сделать вращение всего куба, примените одну и ту же матрицу вращения к каждой части.
Эта реализация проста и имеет несколько тонкостей:
(-1, 1, 1)
), у ребра ровно один ноль ((1, 0, -1)
), а у центрального элемента два ноля ((-1, 0, 0)
).Недостатки:
источник
Вы можете использовать простой массив (каждый элемент имеет отображение 1 к 1 на квадрат на грани) и моделировать каждый поворот с определенной перестановкой
Вы можете избежать трёх существенных перестановок: поверните срез с осью через переднюю грань, поверните куб вокруг вертикальной оси и поверните куб по горизонтальной оси через левую и правую грани. все другие ходы могут быть выражены некоторым объединением этих трех.
самый простой способ узнать, является ли куб разрешимым, - это решить его (найти серию перестановок, которые решат куб), если у вас получится 2 ребра, которые поменялись местами, один перевернутый край, один перевернутый угол или 2 поменялись углами у вас есть неразрешимый куб
источник
the most straightforward way of know whether a cube is solvable is to solve it
, Ну, используя модель, которую вы предлагаете, я думаю, это правда. Но если вы используете модель ближе к @ maple_shaft и отслеживает повороты, вы можете быстро проверить, является ли куб 3x3x3 разрешимым, проверив, что сумма смещений кромок mod 2 равна 0, а угловых поворотов mod 3 равно 0. Затем проверьте четность перестановки с помощью Считая граничные и угловые свопы (необходимо, чтобы вернуться к решению), их сумма mod 2 должна быть 0 (общая четность). Это необходимые и достаточные тесты, чтобы доказать, что куб разрешим.Первое условие, что это может быть решено, должно состоять в том, чтобы присутствовала каждая часть, и чтобы цвета на каждой части могли быть использованы для сборки «совкового» куба. Это относительно тривиальное условие, истинность которого можно определить с помощью простого контрольного списка. Цветовая схема «стандартного» куба определена , но даже если вы не имеете дело со стандартным кубом, их всего 6! возможные комбинации решаемых граней.
Как только у вас все части и цвета будут правильными, тогда решает вопрос, разрешима ли какая-либо конкретная физическая конфигурация. Не все из них. Самый наивный способ проверить это - запустить алгоритм решения куба и посмотреть, заканчивается ли он решенным кубом. Я не знаю, существуют ли причудливые комбинаторные методы для определения разрешимости без фактической попытки решить куб.
Что касается структуры данных ... это почти не имеет значения. Сложность состоит в правильном преобразовании и возможности представить состояние куба таким образом, чтобы вы могли аккуратно работать с доступными алгоритмами в литературе. Как указано в Кленовом валу, существует три типа частей. Литература по решению кубика Рубика всегда относится к частям по их типу. Преобразования также представлены в общих чертах (посмотрите примечание Singmaster ). Кроме того, все решения, которые я видел, всегда ссылаются на одну фигуру в качестве ориентира (обычно помещая белую центральную часть внизу).
источник
Поскольку вы уже получили отличные ответы, позвольте мне добавить только детали.
Независимо от вашего конкретного представления, обратите внимание, что линзы являются очень хорошим инструментом для «увеличения» различных частей куба. Например, посмотрите на функцию
cycleLeft
в этом коде на Haskell . Это универсальная функция, которая циклически переставляет любой список длины 4. Код для выполнения перемещения L выглядит следующим образом:Таким образом,
cycleLeft
действует на мнение, данноеleftCols
. Точно так же,rotateSideCW
которая является универсальной функцией, обращенной к ее повернутой версии, работает с представлением, даннымleftSide
. Другие шаги могут быть реализованы аналогичными способами.Цель библиотеки Haskell - создавать красивые картинки. Я думаю, что это удалось:
источник
Вы, кажется, задаете два отдельных вопроса.
Если вы собираетесь смоделировать кубик Рубика в реальном мире, то все кубики Рубика имеют 6 сторон. Я думаю, что вы имеете в виду "X количество плиток на измерение на сторону". Каждая сторона оригинального кубика Рубика - 3х3. Другие размеры включают 4x4 (куб Профессора), 5x5 и 6x6.
Я хотел бы представить данные с 6 сторон, используя «стандартную» запись решения куба:
Каждая сторона представляет собой двумерный массив X от X.
источник
Мне нравится идея @maple_shaft по-разному представлять разные фигуры (мини-кубы): центральные, краевые и угловые фигуры несут 1, 2 или 3 цвета соответственно.
Я бы представлял отношения между ними в виде (двунаправленного) графа с ребрами, соединяющими соседние элементы. Каждая часть будет иметь массив прорезей для кромок (соединений): 4 прорези в центральной части, 4 прорези в краевых частях, 3 прорези в угловых деталях. В качестве альтернативы, центральные элементы могут иметь 4 соединения с краевыми элементами и 4 для угловых элементов отдельно, и / или краевые элементы могут иметь 2 соединения с центральными элементами и 2 с угловыми элементами отдельно.
Эти массивы упорядочены так, что итерации по краям графа всегда представляют «одно и то же» вращение по модулю вращения куба. То есть, например, для центральной части, если вы поворачиваете куб так, чтобы его грань была сверху, порядок соединений всегда по часовой стрелке. Аналогично для краевых и угловых элементов. Это свойство сохраняется после ротации граней (или мне так кажется сейчас).
Обнаружение явно неразрешимых условий (переставленные / перевернутые края, переставленные углы), если мы надеемся, тоже простое, потому что найти части определенного типа и их ориентацию просто.
источник
Как насчет узлов и указателей?
Предполагая, что всегда есть 6 граней, и этот 1 узел представляет 1 квадрат на 1 грани:
Узел имеет указатель на каждый узел рядом с ним. Вращение круга просто перемещает указатель (Количество узлов / Число граней) на -1 узел, в данном случае 2. Поскольку все вращения являются вращениями окружности, вы просто строите одну
rotate
функцию. Он рекурсивный, перемещает каждый узел на один пробел и проверяет, достаточно ли он их переместил, поскольку он соберет количество узлов, и всегда будет четыре грани. Если нет, увеличьте число перемещенных значений и снова вызовите поворот.Не забывайте, что он дважды связан, поэтому обновите также и новые заостренные узлы. Всегда будет Высота * Ширина Количество перемещаемых узлов, с одним обновленным указателем на узел, поэтому должно быть Высота * Ширина * 2 количества обновленных указателей.
Поскольку все узлы указывают друг на друга, просто ходите по кругу, обновляя каждый узел, когда вы к нему подходите.
Это должно работать для любого размера куба, без крайних случаев или сложной логики. Это просто указатель ходьбы / обновления.
источник
Исходя из личного опыта, использование набора для отслеживания каждой вращающейся части куба работает хорошо. Каждый вложенный куб состоит из трех наборов, независимо от размера кубика Рубика. Таким образом, чтобы найти подкуб, где на кубике Рубика вы просто берете пересечение трех наборов (в результате получается один подкуб). Чтобы сделать ход, удалите затронутых суб кубов из наборов, участвующих в движении, а затем верните их обратно в наборы, которые принимают их в результате движения.
Куб 4 на 4 будет иметь 12 комплектов. 6 комплектов для 6 граней и 6 комплектов для шести полос, которые идут вокруг куба. У граней по 16 субкубов, а у каждой по 12 субкубов. Всего 56 субкубов. Каждый вложенный куб содержит информацию о цвете и направлении цветов. Сам кубик Рубика представляет собой массив 4 на 4 на 4, причем каждый элемент содержит информацию, состоящую из 3 наборов, которые определяют подкуб в этом месте.
В отличие от остальных 11 ответов, в этой структуре данных используется пересечение множеств для определения местоположения каждого подблока в кубе. Это избавляет от необходимости обновления ближайших субблоков при внесении изменений.
источник