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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Это будет выглядеть следующим образом:

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

Вы не могли бы на самом деле нужно 2 «last'-указатели.

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

Answer 9

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

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 

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