data structures - rapida - ¿Cómo representarías un Cubo de Rubik en el código?
cubo rubik solucion rapida (9)
Como una permutación de las 48 caras que pueden moverse. Las rotaciones básicas también son permutaciones, y las permutaciones se pueden componer, forman un grupo.
En un programa, dicha 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, de modo que una representación visual se puede calcular a partir de la permutación, y viceversa.
Si estuvieras desarrollando un software para resolver un cubo de Rubik, ¿cómo representarías el cubo?
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.
Este documento de ACM describe varias formas alternativas que ha utilizado para representar un cubo de rubik y los compara entre sí. Lamentablemente, no tengo una cuenta para obtener el texto completo, pero la descripción dice:
Se presentan y comparan siete representaciones alternativas del Cubo de Rubik: una matriz de 3 dígitos por 3 dígitos; 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 relevante para rotar las secciones (si está buscando un código real). Utiliza una matriz de celda y caras.
Evitar la optimización; hacerlo orientado a objetos Un esquema de clase de 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ña y el procesamiento es tan mínimo que la optimización es totalmente innecesaria, especialmente cuando se sacrifica la usabilidad del código.
Hay 20 cubículos 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 de la etiqueta engomada del logotipo que está en el centro blanco.
Por cierto, ayudé a alguien a hacer un software del cubo de Rubik una vez, tal vez hace 15 años, pero no recuerdo cómo lo representamos.
Hay muchas maneras de hacer esto. Algunas formas son hacer un uso más eficiente de la memoria que otros.
He visto personas usar una matriz de 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 preocupación más grande 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 una 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.
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.
Puede imaginar el cubo como tres listas verticales circulares vinculadas, que se cruzan con tres listas vinculadas horizontales.
Cada vez que una determinada fila del cubo se gira, simplemente rotaría los punteros correspondientes.
Se vería así:
struct cubeLinkedListNode {
cubedLinkedListNode* nextVertical;
cubedLinkedListNode* lastVertical;
cubedLinkedListNode* nextHorizontal;
cubedLinkedListNode* lastHorizontal;
enum color;
}
Es posible que en realidad no necesite los 2 ''últimos'' indicadores.
[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 vinculada correspondiente desplazando secuencialmente los enlaces del círculo giratorio, así como los círculos de conexión.
Algo así, al menos ...
Una forma sería enfocarse en la apariencia visual.
Un cubo tiene seis caras y cada cara es una matriz de cuadrados de tres por tres. Asi que
Color[][][] rubik = new Color[6][3][3];
Entonces, cada movimiento es un método que permuta un conjunto específico de cuadrados de colores.