Cómo representar un cubo de Rubik en una estructura de datos

Si intento simular un Cubo de Rubik , ¿cómo crearía una estructura de datos para almacenar el estado del cubo en la memoria, con un número X de mosaicos por lado?

Cosas para considerar:

• el cubo puede ser de cualquier tamaño
• es un cubo de Rubik, por lo que las capas se pueden rotar

¿Qué hay de malo con una simple matriz de tamaño [6X][X]? No necesita saber acerca de los minicubos internos , porque no los ve; no son parte del estado del cubo. Oculta dos métodos feos detrás de una interfaz agradable y fácil de usar, prueba la unidad hasta la muerte y listo, ¡listo!

Cabe señalar que soy un ávido cubicor de velocidad, pero nunca he intentado representar programáticamente un cubo de Rubik en un algoritmo o estructura de datos.

Probablemente crearía estructuras de datos separadas para capturar los aspectos únicos de cada bloque en un cubo.

Hay 3 tipos distintos de bloques en un cubo:

1. Bloque de esquina: tiene tres caras de color y tres piezas adyacentes con las que compartirá un lado en cualquier momento.

2. Edge Block: tiene dos caras de color y 4 piezas adyacentes con las que compartirá un lado en cualquier momento. En bloques de 3x3 siempre tiene 2 piezas centrales y 2 piezas de esquina.

3. Bloque central: en un cubo de 3x3, esta pieza no es móvil, sin embargo, puede rotarse. Siempre tendrá 4 bloques de borde adyacentes. En cubos más grandes hay múltiples bloques centrales que podrían compartir con otro bloque central o una pieza de borde. Los bloques centrales nunca son adyacentes a un bloque de esquina.

Sabiendo esto, un bloque puede tener una lista de referencias a otros bloques que toca. Mantendría otra lista de listas, que sería una lista de bloques que representan una sola cara de cubo y una lista que mantiene referencias a cada cara de cubo.

Cada cara del cubo se representaría como una cara única.

Con estas estructuras de datos, sería bastante fácil escribir un algoritmo que realice una transformación de rotación en cada cara, moviendo los bloques apropiados dentro y fuera de las listas apropiadas.

EDITAR: Nota importante, estas listas deben ordenarse, por supuesto, pero olvidé mencionar eso. Por ejemplo, si volteo el lado derecho, entonces el bloque del lado derecho de la esquina izquierda se mueve hacia la esquina derecha del lado derecho y se gira en sentido horario.

Cuando pienso en este problema, pienso en un cubo estático con los colores moviéndose a través de él en patrones conocidos. Entonces....

Un objeto Cubo contiene 6 objetos laterales que permanecen fijos indexados 0-5. Cada lado contiene 9 objetos de posición que permanecen fijos indexados 0-8. Cada posición contiene un color.

Para simplificar, maneja cada acción en incrementos de cuarto de vuelta. Hay 3 ejes de rotación, cada uno en 2 direcciones posibles para un total de 6 acciones posibles en el cubo. Con esta información, se convierte en una tarea bastante simple mapear las 6 acciones posibles en el cubo.

Por lo tanto, el color verde en el lado 6, posición 3, puede moverse al lado 1, posición 3, o al lado 2, posición 7, entre otros, dependiendo de la acción tomada. No he explorado esto lo suficiente como para encontrar ninguna traducción matemática, pero probablemente surgirán patrones que puede aprovechar en el código.

Usando la estructura de datos, ¿cómo puedo saber si cierto cubo en cierto estado es solucionable? He estado luchando con esta pregunta yo mismo y todavía no he encontrado la respuesta.

Para hacer esto, nunca comience con un estado de cubo aleatorio. En su lugar, comience con un estado resuelto y realice n acciones mediante programación para llevar el cubo a un estado inicial aleatorio. Como solo tomaste medidas legales para llegar al estado actual, el cubo debe poder resolverse.

Encontré que un sistema de coordenadas xyz es una manera simple de abordar un cubo de Rubik, y las matrices de rotación una forma simple y genérica de implementar las rotaciones.

Creé una clase Piece que contiene un vector de posición (x, y, z). Una pieza se puede girar aplicando una matriz de rotación a su posición (una multiplicación matriz-vector). La pieza también mantiene pistas de sus colores en una tupla (cx, cy, cz), dando los colores que se enfrentan a lo largo de cada eje. Una pequeña cantidad de lógica asegura que estos colores se actualicen adecuadamente durante una rotación: una rotación de 90 grados en el plano XY significa que intercambiaríamos los valores de cxy cy.

Debido a que toda la lógica de rotación está encapsulada en la clase Piece, el Cube puede almacenar una lista desordenada de Piezas, y las rotaciones se pueden hacer de forma genérica. Para hacer una rotación de la cara izquierda, seleccione todas las piezas con una coordenada x de -1 y aplique la matriz de rotación adecuada a cada pieza. Para hacer una rotación de todo el cubo, aplique la misma matriz de rotación a cada pieza.

Esta implementación es simple y tiene un par de sutilezas:

1. La posición de un objeto Piece cambiará, pero sus colores no. Esto significa que puede solicitar la pieza rojo-verde, aferrarse al objeto, hacer algunas rotaciones y verificar el mismo objeto para ver dónde terminó la pieza rojo-verde.
2. Cada tipo de pieza (borde, centro, esquina) tiene un patrón de coordenadas único. Para un cubo de 3x3, una pieza de esquina no tiene ceros en su vector de posición ( (-1, 1, 1)), un borde tiene exactamente un cero ( (1, 0, -1)) y una pieza central tiene dos ceros ( (-1, 0, 0)).
3. Las matrices de rotación que funcionan para un cubo 3x3 funcionarán para un cubo NxN.

Desventajas:

1. La multiplicación de vectores de matriz es más lenta que el intercambio de valores en matrices.
2. Búsquedas de tiempo lineal para piezas por posición. Tendría que almacenar Piezas en una estructura de datos externa y actualizarla durante las rotaciones para búsquedas de tiempo constante por posición. Esto derrota parte de la elegancia del uso de matrices de rotación y filtra la lógica de rotación en su clase de cubo. Si estaba implementando algún tipo de solución basada en búsqueda, usaría otra implementación.
3. El análisis de patrones (durante la resolución) no es tan bueno como podría ser. Una pieza no tiene conocimiento de sus piezas adyacentes, y el análisis sería lento debido a los problemas de rendimiento anteriores.

puede usar una matriz simple (cada elemento tiene un mapeo de 1 a 1 a un cuadrado en una cara) y simular cada rotación con una cierta permutación

puede salirse con solo 3 permutaciones esenciales: gire un corte con el eje a través de la cara frontal, gire el cubo alrededor del eje vertical y gire el cubo sobre el eje horizontal a través de las caras izquierda y derecha. todos los otros movimientos se pueden expresar mediante una concatenación de estos tres.

la forma más directa de saber si un cubo es solucionable es resolverlo (encuentre una serie de permutaciones que resolverán el cubo), si termina con 2 bordes que han cambiado de lugar, un solo borde invertido, una sola esquina invertida o 2 esquinas intercambiadas tienes un cubo que no se puede mover

La primera condición para que sea solucionable sería que cada pieza esté presente y que los colores de cada pieza se puedan usar para ensamblar un cubo "enredado". Esta es una condición relativamente trivial cuya verdad se puede determinar con una simple lista de verificación. El esquema de color en un cubo "estándar" está definido , pero incluso si no está tratando con un cubo estándar, ¡solo hay 6! posibles combinaciones de caras resueltas.

Una vez que tenga todas las piezas y colores correctos, entonces es una cuestión determinar si alguna configuración física es solucionable. No todos ellos son. La forma más ingenua de verificar esto es ejecutar un algoritmo de resolución de cubos y ver si termina con un cubo resuelto. No sé si existen técnicas combinatorias sofisticadas para determinar la capacidad de solución sin realmente tratar de resolver el cubo.

En cuanto a qué estructura de datos ... eso casi no importa. La parte difícil es hacer las transformaciones correctas y poder representar el estado del cubo de una manera que le permita trabajar perfectamente con los algoritmos disponibles en la literatura. Como indicó el eje de arce, hay tres tipos de piezas. La literatura sobre la resolución del cubo de rubik siempre se refiere a piezas por su tipo. Las transformaciones también se representan de manera común (busque la notación Singmaster ). Además, todas las soluciones que he visto siempre se refieren a una pieza como punto de referencia (generalmente colocando la pieza central blanca en la parte inferior).

Como ya recibió excelentes respuestas, permítame agregar solo un detalle.

Independientemente de su representación concreta, tenga en cuenta que las lentes son una herramienta muy buena para "acercar" las diversas partes de un cubo. Por ejemplo, mire la función cycleLeften este código Haskell . Es una función genérica que permuta cíclicamente cualquier lista de longitud 4. El código para realizar el movimiento L se ve así:

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

Así cycleLeftopera en la vista dada por leftCols . Del mismo modo, rotateSideCWque es una función genérica que toma un lado de una versión rotada, opera en la vista dada por leftSide. Los otros movimientos se pueden implementar de manera similar.

El objetivo de esa biblioteca de Haskell es crear imágenes bonitas. Creo que tuvo éxito:

Parece que estás haciendo dos preguntas separadas.

1. ¿Cómo representar un cubo con X número de lados?

Si vas a simular un cubo de Rubic del mundo real, entonces todos los cubos de Rubik tienen 6 lados. Creo que lo que quieres decir es "X número de fichas por dimensión por lado". Cada lado del cubo original de Rubic es 3x3. Otros tamaños incluyen 4x4 (Cubo del profesor), 5x5 y 6x6.

Representaría los datos con 6 lados, usando la notación de resolución de cubos "estándar":

• FRENTE: la cara frente al solucionador
• ESPALDA
• DERECHO
• IZQUIERDA
• ARRIBA
• ABAJO

Cada lado es una matriz bidimensional de X por X.

Me gusta la idea de @maple_shaft para representar diferentes piezas (mini-cubos) de manera diferente: las piezas centrales, de borde y de esquina tienen 1, 2 o 3 colores, respectivamente.

Representaría las relaciones entre ellos como un gráfico (bidireccional), con bordes que conectan piezas adyacentes. Cada pieza tendría una serie de ranuras para bordes (conexiones): 4 ranuras en piezas centrales, 4 ranuras en piezas de borde, 3 ranuras en piezas de esquina. Alternativamente, las piezas centrales pueden tener 4 conexiones a las piezas de borde y 4 para las piezas de esquina por separado, y / o las piezas de borde pueden tener 2 conexiones a las piezas centrales y 2 a las piezas de esquina por separado.

Estas matrices están ordenadas de modo que iterar sobre los bordes del gráfico siempre represente la 'misma' rotación, módulo la rotación del cubo. Es decir, por ejemplo, para una pieza central, si gira el cubo de modo que su cara esté en la parte superior, el orden de las conexiones siempre es en el sentido de las agujas del reloj. Del mismo modo para las piezas de borde y esquina. Esta propiedad se mantiene después de las rotaciones de la cara (o eso me parece ahora).

• Encontrar piezas que pertenecen a un borde es trivial.
• Encontrar piezas que pertenecen a una cara es trivial.
• Encontrar caras que están en la dirección dada a una cara dada, o una cara opuesta, está atravesando 2 o 3 enlaces bien definidos.
• Para rotar una cara, actualice las conexiones de todas las piezas conectadas a la pieza central de la cara.

Detección de condiciones claramente insolubles (bordes intercambiados / volteados, esquina intercambiada) si es de esperar, también, porque encontrar piezas de un tipo particular y su orientación es simple.

¿Qué hay de nodos y punteros?

Suponiendo que siempre haya 6 caras y que 1 nodo represente 1 cuadrado en 1 cara:

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

Un nodo tiene un puntero a cada nodo al lado. Una rotación circular solo migra el puntero (Número de nodos / Número de caras) -1 nodos, en este caso 2. Dado que todas las rotaciones son rotaciones circulares, simplemente construye una rotatefunción. Es recursivo, mueve cada nodo un espacio y comprueba si los ha movido lo suficiente, ya que habrá recogido el número de nodos, y siempre hay cuatro caras. De lo contrario, incremente el número de veces que se movió el valor y la llamada rotará nuevamente.

No olvide que está doblemente vinculado, así que actualice también los nodos recién apuntados. Siempre habrá Altura * Ancho número de nodos movidos, con un puntero actualizado por nodo, por lo que debería haber Altura * Ancho * 2 número de punteros actualizados.

Dado que todos los nodos se apuntan entre sí, simplemente camine en círculo actualizando cada nodo a medida que se acerca.

Esto debería funcionar para cualquier tamaño de cubo, sin casos extremos o lógica compleja. Es solo una caminata / actualización de puntero.

Desde la experiencia personal, el uso de un conjunto para realizar un seguimiento de cada parte rotacional del cubo funciona bien. Cada subcubo está en tres conjuntos sin importar el tamaño del cubo de rubik. Entonces, para encontrar un subcubo en algún lugar del cubo de Rubik, simplemente tome la intersección de los tres conjuntos (el resultado es un subcubo). Para hacer un movimiento, elimine los subcubos afectados de los conjuntos involucrados en el movimiento y luego vuelva a colocarlos en los conjuntos que los toman como resultado del movimiento.

El cubo de 4 por 4 tendrá 12 juegos. 6 juegos para las 6 caras y 6 juegos para las seis bandas que rodean el cubo. Las caras tienen 16 subcubos y las bandas tienen 12 subcubos. Hay un total de 56 sub cubos. Cada subcubo contiene información sobre el color y la dirección de los colores. El propio cubo de Rubik es una matriz de 4 por 4 por 4 con cada elemento que tiene información que consta de los 3 conjuntos que definen el subcubo en esa ubicación.

A diferencia de las otras 11 respuestas, esta estructura de datos lo hace usar la intersección de conjuntos para definir la ubicación de cada subbloque en el cubo. Esto ahorra el trabajo de tener que actualizar los subbloques cercanos cuando se realiza un cambio.