Как представить кубик Рубика в структуре данных

58

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

Что нужно учитывать:

  • куб может быть любого размера
  • это кубик Рубика, поэтому слои можно вращать
Мел
источник
2
Домашнее задание? Или проблема реального мира ...
SDG
4
Возможно, вас заинтересует исходный код решателя кубиков Рубика .
mouviciel
22
Я почти уверен, что число сторон куба должно быть 6
Саймон Бергот
3
Мне было бы любопытно увидеть, как модель Кубика Рубика сплющена, чтобы я мог видеть все стороны одновременно. Хм, я испытываю желание написать это сейчас. Это может быть форма буквы T или даже бесконечная черепица, если это возможно (я не продумал последний вариант).
Ли Ковальковски
6
У меня возникает соблазн процитировать Эрика Эванса: «Модели не являются ни правильными, ни неправильными. Они просто более или менее полезны» (цитата, вероятно, не на 100% правильная, как цитируется по памяти)
Пит

Ответы:

37

Что не так с простым старым массивом размера [6X][X]? Вам не нужно знать о внутренних мини-кубах, потому что вы их не видите; они не являются частью состояния куба. Скройте два уродливых метода за красивым и простым в использовании интерфейсом, протестируйте его до смерти и вуаля, все готово!

dasblinkenlight
источник
31
даже настоящий кубик Рубика не имеет внутренних мини-кубов
jk.
8
Это будет работать, но ваш алгоритм, вероятно, будет чрезмерно сложным для размещения такой простой структуры данных.
maple_shaft
6
As long as you know how the six surfaces are "threaded" together Именно это даст вам более надежная структура данных. Я думаю, что мы спорим об одном и том же. Стороны массива, а сторона - это массив блоков, однако есть много интересных свойств относительно сторон и блоков, которые помогают понять, что «многопоточность» Этот термин не очень нравится, потому что его можно спутать с многопоточностью; )
maple_shaft
7
@maple_shaft "Это именно то, что даст вам более надежная структура данных." Я не знаю об этом: структура данных с большей «структурой» обязательно вызовет дополнительную случайную сложность, связанную с настройкой, поддержкой и доступом к отдельным частям этой структуры. Трудно сказать, что было бы более сложным - реализация некрасивых сдвигов в простом массиве с некоторыми угловыми случаями плюс «свободный переход» при доступе к отдельным ячейкам или структура с несколько менее сложными сдвигами и несколько более сложным чтением.
dasblinkenlight
16
Как человек, который на самом деле написал программы для манипулирования кубиком Рубика, я выбрал простой подход - использовать шесть двумерных массивов, по одному на лицо. Это правда, что вам нужно реализовать некоторые фундаментальные операции с кубом, которые немного раздражают, но после этого вы можете забыть о представлении. Это никогда не было проблемой для меня. Я часто задавался вопросом, как другие представления будут работать с точки зрения производительности, но никогда не чувствовал себя обремененным с точки зрения кодирования.
PeterAllenWebb
39

Следует отметить, что я страстный любитель скорости, но я никогда не пытался программно представлять кубик Рубика в алгоритме или структуре данных.

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

В кубе есть 3 различных типа блоков:

  1. Угловой блок - у него есть три цветных грани и три смежные части, с которыми он будет разделять сторону в любое время.

  2. Edge Block - имеет две цветные грани и имеет 4 смежных фигуры, с которыми у него будет общая сторона в любое время. В блоках 3х3 всегда 2 центральных и 2 угловых.

  3. Центральный блок - в кубе 3х3 эта часть не подвижна, однако ее можно вращать. У него всегда будет 4 смежных краевых блока. В больших кубах есть несколько центральных блоков, которые могут делиться с другим центральным блоком или краевой частью. Центральные блоки никогда не примыкают к угловому блоку.

Зная это, у Блока может быть список ссылок на другие блоки, к которым он прикасается. Я бы сохранил другой список списков, который был бы списком блоков, представляющих одну грань куба, и списком, в котором хранятся ссылки на каждую грань куба.

Каждое лицо куба будет представлено как уникальное лицо.

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

РЕДАКТИРОВАТЬ: Важное примечание, эти списки должны быть заказаны, конечно, но я забыл упомянуть об этом. Например, если я переверну правую сторону, то левый угловой блок правой стороны переместится в правый угол правой стороны и повернется по часовой стрелке.

maple_shaft
источник
согласитесь, что каждый блок должен иметь уникальные свойства. но преобразование не будет утомительным, потому что вы должны обновить ссылки на соседние блоки и ваши list of lists. может быть, лучше просто иметь неупорядоченный список блоков, которые вы можете запросить. и вы просто обновляете ссылки на соседние блоки при выполнении преобразования. Если вы хотите получить список всех блоков на грани, вы можете запросить список всех смежных блоков в центральном блоке (ах), верно?
Мел
@Mel Можно сделать это в любом случае, но после разговора с dasblinkenlight я действительно думаю, что его подход будет менее сложным. Я бы хотел, чтобы у его ответа было больше голосов, чем у меня. Я не так хорош в алгоритмах и не самый эффективный, я просто очень люблю кубики Рубика и собираю их (более 40 различных видов со всего мира).
maple_shaft
Хотя dasblinknenlight ответит самое простое решение, я награждаю вас щедростью, потому что мне нравится тот факт, что ваш ответ включает в себя некоторую логику, которая потребуется для такой структуры данных, и различные атрибуты блока
Рэйчел
Эта модель данных более соответствует действительности, но она делает некоторые из простых операций, которые вы хотели бы выполнять, сложнее, чем они должны быть - просто получение состояния куба потребовало бы рекурсивного перемещения по спискам кубов, что является громоздким.
Зив
@Ziv Верно, однако вопрос был о структуре данных, а не об алгоритмах.
maple_shaft
13

Когда я думаю об этой проблеме, я думаю о статическом кубе с цветами, движущимися по нему известными узорами. Так....

Объект Cube содержит 6 объектов Side, которые остаются фиксированными с индексами 0-5. Каждая сторона содержит 9 объектов позиции, которые остаются фиксированными с индексами 0-8. Каждая позиция содержит цвет.

Для простоты обрабатывайте каждое действие с шагом в четверть оборота. Есть 3 оси вращения, каждая в 2 возможных направлениях, всего 6 возможных действий на кубе. С этой информацией становится довольно простой задачей наметить 6 возможных действий на кубе.

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

Используя структуру данных, как я могу узнать, разрешим ли определенный куб в определенном состоянии? Я сам боролся с этим вопросом и пока не нашел ответа.

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

Мэтью Вайнс
источник
1
Классический совет «не хочешь начинать отсюда»!
Эргвун
8

Я обнаружил, что система координат XYZ - это простой способ обращения к кубу Рубика, а матрицы вращения - простой, общий способ реализации вращений.

Я создал класс Piece, содержащий вектор позиции (x, y, z). Кусок можно вращать, применяя к его положению матрицу вращения (умножение матрицы на вектор). Пьеса также отслеживает цвета в кортеже (cx, cy, cz), давая цвета, обращенные вдоль каждой оси. Небольшое количество логики обеспечивает правильное обновление этих цветов во время поворота: поворот на 90 градусов в плоскости XY означает, что мы должны поменять местами значения cxи cy.

Поскольку вся логика вращения инкапсулирована в классе Piece, Cube может хранить неупорядоченный список Pieces, и вращения могут выполняться в общем виде. Чтобы сделать поворот левой грани, выберите все фигуры с координатой х -1 и примените соответствующую матрицу вращения к каждой фигуре. Чтобы сделать вращение всего куба, примените одну и ту же матрицу вращения к каждой части.

Эта реализация проста и имеет несколько тонкостей:

  1. Положение объекта Piece изменится, а его цвета - нет. Это означает, что вы можете попросить красно-зеленый предмет, повесить на объект, сделать несколько поворотов и проверить тот же объект, чтобы увидеть, где оказался красно-зеленый предмет.
  2. Каждый тип фигуры (ребро, центр, угол) имеет уникальный шаблон координат. Для куба 3x3 угловой элемент не имеет нулей в своем векторе положения ( (-1, 1, 1)), у ребра ровно один ноль ( (1, 0, -1)), а у центрального элемента два ноля ( (-1, 0, 0)).
  3. Матрицы вращения, которые работают для куба 3x3, будут работать для куба NxN.

Недостатки:

  1. Умножение матрицы на вектор происходит медленнее, чем перестановка значений в массивах.
  2. Линейное время поиска пьес по позиции. Вам нужно будет хранить кусочки во внешней структуре данных и обновлять ее во время поворотов для постоянного поиска по позиции. Это лишает элегантности использования матриц вращения и пропускает логику вращения в ваш класс Cube. Если бы я реализовывал какой-либо алгоритм поиска на основе поиска, я бы использовал другую реализацию.
  3. Анализ паттернов (во время решения) не так хорош, как мог бы быть. Часть не знает о смежных частях, и анализ будет медленным из-за вышеуказанных проблем с производительностью.
user156217
источник
3
Я обнаружил, что этот вид реализации лучше всего подходит для представления куба в программе 3D-графики. Умножение матриц позволяет анимировать вращения слоев. Посмотрите это репозиторий github для примера реализации этого подхода. Я считаю, что для добавления решателя в мой 3D-куб мне понадобится алгоритм и структура данных из одного из других ответов.
Джонатан Уилсон
5

Вы можете использовать простой массив (каждый элемент имеет отображение 1 к 1 на квадрат на грани) и моделировать каждый поворот с определенной перестановкой

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

самый простой способ узнать, является ли куб разрешимым, - это решить его (найти серию перестановок, которые решат куб), если у вас получится 2 ребра, которые поменялись местами, один перевернутый край, один перевернутый угол или 2 поменялись углами у вас есть неразрешимый куб

чокнутый урод
источник
1
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 (общая четность). Это необходимые и достаточные тесты, чтобы доказать, что куб разрешим.
Джимхарк
3

Первое условие, что это может быть решено, должно состоять в том, чтобы присутствовала каждая часть, и чтобы цвета на каждой части могли быть использованы для сборки «совкового» куба. Это относительно тривиальное условие, истинность которого можно определить с помощью простого контрольного списка. Цветовая схема «стандартного» куба определена , но даже если вы не имеете дело со стандартным кубом, их всего 6! возможные комбинации решаемых граней.

Как только у вас все части и цвета будут правильными, тогда решает вопрос, разрешима ли какая-либо конкретная физическая конфигурация. Не все из них. Самый наивный способ проверить это - запустить алгоритм решения куба и посмотреть, заканчивается ли он решенным кубом. Я не знаю, существуют ли причудливые комбинаторные методы для определения разрешимости без фактической попытки решить куб.

Что касается структуры данных ... это почти не имеет значения. Сложность состоит в правильном преобразовании и возможности представить состояние куба таким образом, чтобы вы могли аккуратно работать с доступными алгоритмами в литературе. Как указано в Кленовом валу, существует три типа частей. Литература по решению кубика Рубика всегда относится к частям по их типу. Преобразования также представлены в общих чертах (посмотрите примечание Singmaster ). Кроме того, все решения, которые я видел, всегда ссылаются на одну фигуру в качестве ориентира (обычно помещая белую центральную часть внизу).

Angelo
источник
1
Для пункта 2 вместо того, чтобы начинать со случайного куба и проверять, разрешим ли он. Я бы начал с решенного куба и выполнил бы n случайных действий с кубом, чтобы перевести его в случайное состояние.
Мэтью Вайнс
Да, безусловно, это самый простой способ создать конфигурацию, которую физически возможно решить. Начиная с произвольной конфигурации и определяя, является ли она разрешимой, это определенно отдельная, но связанная проблема.
Анджело
2
Вы предполагаете, что могут существовать «причудливые методы» для определения того, может ли быть решен куб; на самом деле есть. Если вы разбираете куб, но держите наклейки, а затем снова собираете куб, вы не обязательно получите куб, который разрешим; на самом деле шансы от одного до двенадцати против того, что у вас есть разрешимый куб. Вы можете определить, находитесь ли вы в разрешимом состоянии, с помощью анализа четности краев и углов; вам на самом деле не нужно пытаться решить куб.
Эрик Липперт
1
Вот краткий обзор трех видов свойств парности кубов, которые необходимо сохранить, чтобы куб был разрешимым. ryanheise.com/cube/cube_laws.html .
Эрик Липперт
1
Я разместил этот вопрос на сайте матча stackexchange и получил действительно хорошие ответы: math.stackexchange.com/questions/127577/…
Mel
3

Поскольку вы уже получили отличные ответы, позвольте мне добавить только детали.

Независимо от вашего конкретного представления, обратите внимание, что линзы являются очень хорошим инструментом для «увеличения» различных частей куба. Например, посмотрите на функцию cycleLeftв этом коде на Haskell . Это универсальная функция, которая циклически переставляет любой список длины 4. Код для выполнения перемещения L выглядит следующим образом:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

Таким образом, cycleLeftдействует на мнение, данное leftCols . Точно так же, rotateSideCWкоторая является универсальной функцией, обращенной к ее повернутой версии, работает с представлением, данным leftSide. Другие шаги могут быть реализованы аналогичными способами.

Цель библиотеки Haskell - создавать красивые картинки. Я думаю, что это удалось: Библиотека Diagrams-Rubiks-Cube в действии

Инго Блехшмидт
источник
2

Вы, кажется, задаете два отдельных вопроса.

  1. Как изобразить куб с числом сторон X?

Если вы собираетесь смоделировать кубик Рубика в реальном мире, то все кубики Рубика имеют 6 сторон. Я думаю, что вы имеете в виду "X количество плиток на измерение на сторону". Каждая сторона оригинального кубика Рубика - 3х3. Другие размеры включают 4x4 (куб Профессора), 5x5 и 6x6.

Я хотел бы представить данные с 6 сторон, используя «стандартную» запись решения куба:

  • FRONT: лицо, обращенное к решателю
  • НАЗАД
  • ПРАВИЛЬНО
  • ОСТАВИЛ
  • UP
  • ВНИЗ

Каждая сторона представляет собой двумерный массив X от X.

Б Семь
источник
Вы можете купить куб 17x17 ! У него есть некоторые механические компромиссы, но он изоморфен реальному.
RBerteig
1

Мне нравится идея @maple_shaft по-разному представлять разные фигуры (мини-кубы): центральные, краевые и угловые фигуры несут 1, 2 или 3 цвета соответственно.

Я бы представлял отношения между ними в виде (двунаправленного) графа с ребрами, соединяющими соседние элементы. Каждая часть будет иметь массив прорезей для кромок (соединений): 4 прорези в центральной части, 4 прорези в краевых частях, 3 прорези в угловых деталях. В качестве альтернативы, центральные элементы могут иметь 4 соединения с краевыми элементами и 4 для угловых элементов отдельно, и / или краевые элементы могут иметь 2 соединения с центральными элементами и 2 с угловыми элементами отдельно.

Эти массивы упорядочены так, что итерации по краям графа всегда представляют «одно и то же» вращение по модулю вращения куба. То есть, например, для центральной части, если вы поворачиваете куб так, чтобы его грань была сверху, порядок соединений всегда по часовой стрелке. Аналогично для краевых и угловых элементов. Это свойство сохраняется после ротации граней (или мне так кажется сейчас).

  • Поиск частей, принадлежащих ребру, тривиален.
  • Поиск фигур, принадлежащих лицу, тривиален.
  • Поиск граней, которые находятся в заданном направлении к данной грани или противоположной грани, пересекает 2 или 3 четко определенных ссылки.
  • Чтобы повернуть грань, обновите соединения всех частей, соединенных с центральной частью лица.

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

9000
источник
1

Как насчет узлов и указателей?

Предполагая, что всегда есть 6 граней, и этот 1 узел представляет 1 квадрат на 1 грани:

r , g , b
r , g , b
r , g , b
|   |   |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b

Узел имеет указатель на каждый узел рядом с ним. Вращение круга просто перемещает указатель (Количество узлов / Число граней) на -1 узел, в данном случае 2. Поскольку все вращения являются вращениями окружности, вы просто строите одну rotateфункцию. Он рекурсивный, перемещает каждый узел на один пробел и проверяет, достаточно ли он их переместил, поскольку он соберет количество узлов, и всегда будет четыре грани. Если нет, увеличьте число перемещенных значений и снова вызовите поворот.

Не забывайте, что он дважды связан, поэтому обновите также и новые заостренные узлы. Всегда будет Высота * Ширина Количество перемещаемых узлов, с одним обновленным указателем на узел, поэтому должно быть Высота * Ширина * 2 количества обновленных указателей.

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

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

Спенсер Рэтбун
источник
-1

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

Куб 4 на 4 будет иметь 12 комплектов. 6 комплектов для 6 граней и 6 комплектов для шести полос, которые идут вокруг куба. У граней по 16 субкубов, а у каждой по 12 субкубов. Всего 56 субкубов. Каждый вложенный куб содержит информацию о цвете и направлении цветов. Сам кубик Рубика представляет собой массив 4 на 4 на 4, причем каждый элемент содержит информацию, состоящую из 3 наборов, которые определяют подкуб в этом месте.

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

сильный мученик
источник
кажется, это не дает ничего существенного по сравнению с замечаниями, сделанными и объясненными в предыдущих 11 ответах
комнат