Si estoy intentando simular un Rubik's Cube , ¿cómo crearía una estructura de datos para almacenar el cubo? Estado en la memoria, con X número de fichas por lado?
Cosas a considerar:
¿Qué tiene de malo una matriz antigua y lisa de tamaño [6X][X] ? No necesita saber acerca de los mini cubos internos , porque no los ve; no son parte del estado del cubo. Oculta dos métodos feos detrás de una interfaz atractiva y fácil de usar, prueba la unidad hasta la muerte y listo, ¡listo!
Cabe señalar que soy un ávido motor 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:
Bloque de esquina: tiene tres caras de color y tres piezas adyacentes con las que compartirá un lado en cualquier momento.
Bloque de bordes: tiene dos caras de color y tiene 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.
Bloque central: en un cubo de 3x3, esta pieza no es movible, sin embargo, puede girarse. Siempre tendrá 4 bloques de borde adyacentes. En cubos más grandes hay varios bloques centrales que podrían compartir con otro bloque central o una pieza de borde. Los bloques centrales nunca están 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 única cara de cubo y una lista que mantiene referencias a cada cara de cubo.
Cada cara de 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 doy la vuelta al lado derecho, el bloque del lado derecho de la esquina izquierda se mueve hacia la esquina derecha del lado derecho y se gira hacia la derecha.
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.
Por simplicidad, maneje cada acción en incrementos de un 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 para trazar las 6 acciones posibles en el cubo.
Por lo tanto, el color verde en el lado 6, posición 3, puede moverse hacia el lado 1 posición 3, o el lado 2 posición 7, entre otros, según la acción realizada. No he explorado esto lo suficiente como para encontrar ninguna traducción matemática, pero es probable que surjan patrones que puedas aprovechar en el código.
Utilizando la estructura de datos, ¿cómo puedo saber si un determinado cubo en un 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 las acciones de n mediante programación para que el cubo tenga un estado de inicio aleatorio. Dado que solo tomó acciones legales para llegar al estado actual, el cubo debe poder resolverse.
Descubrí que un sistema de coordenadas x-y-z es una forma simple de abordar el cubo de Rubik, y las matrices de rotación son 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 puede rotarse aplicando una matriz de rotación a su posición (una multiplicación de matriz-vector). La pieza también mantiene las pistas de los colores en una tupla (cx, cy, cz) , dando los colores orientados a lo largo de cada eje. Una pequeña cantidad de lógica garantiza que estos colores se actualicen adecuadamente durante una rotación: una rotación de 90 grados en el plano X-Y significa que intercambiaremos los valores de cx y cy .
Debido a que toda la lógica de rotación está encapsulada en la clase de Pieza, el Cubo puede almacenar una lista desordenada de Piezas, y las rotaciones se pueden hacer de manera 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 detalles:
(-1, 1, 1) ), una arista tiene exactamente un cero ( (1, 0, -1) ) y una pieza central tiene dos ceros ( (-1, 0, 0) ). Desventajas:
puede usar una matriz simple (cada elemento tiene una asignación 1 a 1 a un cuadrado en una cara) y simular cada rotación con una cierta permutación
puede obtener 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 alguna concatenación de estos tres.
la forma más sencilla de saber si un cubo es solucionable es resolverlo (encuentra una serie de permutaciones que resolverán el cubo), si terminas con 2 bordes que han cambiado de lugar, un solo borde volteado, un solo En la esquina volteada o en 2 esquinas intercambiadas, tienes un cubo que no se puede mover
La primera condición para que se pueda solventar es que cada pieza esté presente y que se puedan usar colores en cada pieza para ensamblar un cubo "sovled". 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 el cubo estándar solo hay 6! posibles combinaciones de caras resueltas.
Una vez que tenga todas las piezas y los colores correctos, es una cuestión que determina si alguna configuración física dada 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 solvencia sin intentar realmente resolver el cubo.
En cuanto a qué estructura de datos ... eso casi no importa. La parte difícil es hacer las transformaciones correctas y ser capaz de representar el estado del cubo de una manera que le permita trabajar de manera ordenada con los algoritmos disponibles en la literatura. Como indica el árbol de arce hay tres tipos de piezas. La literatura sobre la resolución de cubos de Rubik siempre se refiere a piezas por su tipo. Las transformaciones también se representan de manera común (busque notación Singmaster ). Además, todas las soluciones que he visto siempre se refieren a una pieza como un 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 lentes es una herramienta muy fina para "acercar" las distintas partes de un cubo. Por ejemplo, mire la función cycleLeft en 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 parece a esto:
moveL :: Aut (RubiksCube a)
moveL =
cong cube $ cong leftCols cycleLeft
. cong leftSide rotateSideCW
Por lo tanto, cycleLeft opera en la vista dada por leftCols . De manera similar, rotateSideCW , que es una función genérica que tiene un lado en 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 Haskell es crear imágenes bonitas. Creo que tuvo éxito:
Parece que estás haciendo dos preguntas separadas.
- ¿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 mosaicos por dimensión por lado". Cada lado del cubo de Rubic original es 3x3. Otros tamaños incluyen 4x4 (Professor's Cube), 5x5 y 6x6.
Representaría los datos con 6 lados, usando la notación de resolución de cubo "estándar":
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 llevan 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 la iteración sobre los bordes del gráfico siempre represente "la misma" rotación, modulo 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 hacia la derecha. Del mismo modo para piezas de borde y esquina. Esta propiedad se mantiene después de las rotaciones de caras (o eso me parece ahora).
Detección de condiciones claramente insolubles (bordes intercambiados / volteados, esquinas intercambiadas) si se espera que también sean fáciles, porque encontrar piezas de un tipo particular y su orientación es simple.
¿Qué hay de los nodos y los punteros?
Suponiendo que siempre hay 6 caras, y que 1 nodo representa 1 casilla 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 junto a él. Una rotación de círculo simplemente migra el puntero (Número de nodos / Número de caras) -1 nodos sobre, en este caso 2. Dado que todas las rotaciones son rotaciones de círculo, solo se genera una función rotate . Es recursivo, moviendo cada nodo un espacio y verificando si los ha movido lo suficiente, ya que habrá recolectado 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 vuelva a llamar a rotar.
No olvide que está doblemente vinculado, así que actualice también los nodos recién apuntados. Siempre habrá Altura * Ancho de los 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 por el círculo actualizando cada nodo a medida que se acerca.
Esto debería funcionar para cualquier cubo de tamaño, sin casos de borde o lógica compleja. Es solo un puntero a pie / actualización.
Desde la experiencia personal, el uso de un conjunto para realizar un seguimiento de cada parte de rotación del cubo funciona bien. Cada cubo secundario está en tres conjuntos, sin importar el tamaño del cubo Rubik. Entonces, para encontrar un cubo secundario en algún lugar del cubo de Rubik, simplemente toma la intersección de los tres conjuntos (el resultado es un cubo secundario). Para hacer un movimiento, elimine los sub cachorros 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 sets. 6 sets para las 6 caras y 6 sets para las seis bandas que rodean el cubo. Cada cara tiene 16 cubos secundarios y cada banda tiene 12 cubos secundarios. Hay un total de 56 sub cubos. Cada subcubo contiene información sobre el color y la dirección de los colores. El cubo Rubik en sí mismo es una matriz de 4 por 4 por 4, y cada elemento tiene información que consiste en los 3 conjuntos que definen el subcubo en esa ubicación.
A diferencia de las otras 11 respuestas, esta estructura de datos te hace usar la intersección de conjuntos para definir cada ubicación de subbloques en el cubo. Esto ahorra el trabajo de tener que actualizar los sub bloques cercanos cuando se realiza un cambio.
Lea otras preguntas en las etiquetas data-structures