¿Cómo representarías un cubo de Rubik en el código?

Question

Si estuviera desarrollando un software para resolver un cubo de Rubik, ¿cómo representaría el cubo?

Answer 1

Hay muchas formas de hacerlo. Algunas formas son hacer un uso más eficiente de la memoria que otros.

He visto personas usar una matriz 3 x 3 x 3 de objetos cuboides, donde el objeto cuboide necesita almacenar información de color (y sí, ese objeto central nunca se usa). He visto personas usar 6 matrices, cada una de las cuales es una matriz de 3 x 3 de cuboides. He visto una matriz de 3 x 18 de cuboides. Hay muchas posibilidades

Probablemente una mayor preocupación es cómo representar las diversas transformaciones. Girar una sola cara de un cubo físico (todos los movimientos del cubo son esencialmente rotaciones de una sola cara) tendría que representarse al intercambiar muchos objetos cuboides.

Su elección debe ser aquella que tenga sentido para cualquier aplicación que esté escribiendo. Puede ser que solo estés renderizando el cubo. Puede ser que no haya UI. Usted puede estar solucionando el cubo.

Yo elegiría la matriz de 3 x 18.

Answer 2

Una forma sería centrarse en la apariencia visual.

Un cubo tiene seis caras y cada cara es una matriz de cuadrados de tres por tres. Entonces

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

Luego, cada movimiento es un método que permuta un conjunto específico de cuadrados de colores.

Answer 3

Puede imaginar el cubo como tres listas verticales vinculadas circulares, que se cruzan con tres listas vinculadas horizontales.

Cada vez que se gira una cierta fila del cubo, simplemente rotaría los punteros correspondientes.

Se vería así:

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

En realidad, no puede ser que necesite la 2 'last' triples.

[Hice esto con C, pero podría hacerse en Java o C# simplemente usando una clase simple para cubeLinkedListNode, con cada clase con referencias a otros nodos. ]

Recuerde que hay seis listas vinculadas de enlaces circulares. 3 verticales 3 horizontales.

Para cada rotación, simplemente recorrerá la lista circular correspondiente desplazando secuencialmente los enlaces del círculo giratorio, así como los círculos de conexión.

Algo así, al menos ...

Answer 4

Hay 20 cubitos que importan. Entonces, una forma de hacerlo es como una matriz de 20 cadenas. Las cuerdas tienen 2 o 3 caracteres que indican los colores. Cualquier movimiento individual afecta a 7 de los cubículos. Entonces solo necesitas un remapeador para cada uno de los seis lados.

Nota: Esta solución no logra recordar la orientación del adhesivo del logotipo que está en el centro blanco.

Por cierto, ayudé a alguien a hacer un software del cubo de Rubik una vez, quizás hace 15 años, pero no recuerdo cómo lo representamos.

Answer 5

ACM Paper describe varias formas alternativas que ha utilizado para representar un cubo de rubik y los compara entre sí. Desafortunadamente, no tengo una cuenta para obtener el texto completo, pero la descripción dice:

Se presentan y comparan siete representaciones alternativas de Rubik's Cube: una matriz de 3 por 3 por 3 de 3 dígitos enteros; una matriz de literales de 6 por 3 por 3; una matriz literal de 5 por 12; una matriz literal dispersa por todos los niveles; un vector de 54 elementos; una matriz de 4 dimensiones; y una matriz anidada de 3 por 3 por 3. Las funciones APL se dan para movimientos de orientación y cuartos de vuelta más varias herramientas útiles para resolver el cubo.

Además, este archivo RubiksCube.java contiene una representación bastante clara junto con el código correspondiente para rotar las secciones (si está buscando un código real). Utiliza una matriz de celda y caras.

Answer 6

Los otros bien abordados que describen el cubo físico, pero con respecto al estado del cubo ... Intentaré usar una matriz de transformaciones vectoriales para describir los cambios del cubo. De esta forma, podría conservar el historial del cubo rubik mientras se realizan los cambios. Y me pregunto si podría multiplicar los vectores en una matriz de transformación para encontrar la solución más simple.

Answer 7

Como una permutación de las 48 caras que se pueden mover. Las rotaciones básicas también son permutaciones, y las permutaciones se pueden componer, forman un grupo.

En un programa, tal permutación estaría representada por una matriz de 48 elementos que contienen los números 0 a 47. Los colores correspondientes a los números son fijos, por lo que se puede calcular una representación visual a partir de la permutación y viceversa.

Answer 8

El software "Cube Explorer" utiliza un método interesante para representar el cubo. Usando muchas matemáticas inteligentes, ese método puede representar el cubo usando solo 5 enteros. El autor explica las matemáticas detrás de su programa en su website. Según el autor, la representación es adecuada para implementar solucionadores rápidos.

Answer 9

Evitar la optimización; hacerlo orientado a objetos Un esquema de la clase pseudocódigo que he usado es:

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 

La cantidad de memoria utilizada es tan pequeño y tan mínima que el procesamiento de optimización es totalmente innecesario, especialmente cuando se sacrifica código de usabilidad.