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

58

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
Mel
fuente
2
¿Deberes? O un problema del mundo real ...
SDG
44
Puede que le interese el código fuente de ese Solucionador de cubos de Rubik .
mouviciel
22
Estoy bastante seguro de que el número de lados de un cubo debe ser 6
Simon Bergot
3
Sentiría curiosidad por ver un modelo del Cubo de Rubik aplanado para poder ver todos los lados simultáneamente. Hmm, estoy tentado de escribir eso ahora. Podría ser la forma de una T o incluso mosaico sin fin si es posible (no he pensado en esto último).
Lee Kowalkowski el
66
Me siento tentado a citar a Eric Evans, "Los modelos no son ni correctos ni incorrectos. Simplemente son más o menos útiles" (es probable que la cita no sea 100% correcta como se cita de memoria)
Pete

Respuestas:

37

¿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!

dasblinkenlight
fuente
31
incluso un verdadero cubo de Rubik no tiene ningún mini-cubo interno
jk.
8
Esto funcionará, pero su algoritmo probablemente será excesivamente complejo para acomodar una estructura de datos tan simple.
maple_shaft
66
As long as you know how the six surfaces are "threaded" together Que es exactamente lo que le dará una estructura de datos más robusta. Creo que estamos discutiendo por lo mismo. Un conjunto de lados, y un lado es un conjunto de bloques, sin embargo, hay muchas propiedades interesantes sobre los lados y los bloques que ayudan a descubrir que "enhebrar" . )
maple_shaft
77
@maple_shaft "Que es exactamente lo que te dará una estructura de datos más robusta". No sé sobre eso: una estructura de datos con más "estructura" necesariamente generaría una complejidad incidental adicional relacionada con la configuración, el mantenimiento y el acceso a partes individuales de esa estructura. Es difícil decir qué sería más complejo: implementar cambios feos en una matriz simple con algunos casos de esquina más un "recorrido libre" al acceder a celdas individuales, o una estructura con cambios algo menos complejos y lecturas algo más complejas.
dasblinkenlight
16
Como alguien que realmente ha escrito programas para manipular un cubo de Rubik, adopté el enfoque simple de usar seis matrices bidimensionales, una por cara. Es cierto que debe implementar algunas operaciones fundamentales en el cubo que son un poco molestas, pero después de eso puede olvidarse de la representación. Nunca fue un problema para mí. A menudo me preguntaba cómo funcionarían otras representaciones desde una perspectiva de rendimiento, pero nunca me sentí abrumado desde una perspectiva de codificación.
PeterAllenWebb
39

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.

maple_shaft
fuente
de acuerdo en que cada bloque debería tener propiedades únicas. pero la transformación no sería tediosa porque tienes que actualizar las referencias a los bloques adyacentes y tu list of lists. tal vez sea mejor tener una lista desordenada de bloques que puede consultar. y simplemente actualiza las referencias de bloque adyacentes cuando realiza una transformación. Si desea una lista de todos los bloques en una cara, puede consultar en su lista todos los bloques adyacentes a los bloques centrales, ¿verdad?
Mel
@Mel Es posible hacerlo de cualquier manera, pero después de hablar con dasblinkenlight, creo que su enfoque sería menos complejo. Desearía que su respuesta tuviera más votos que la mía. No soy tan bueno con los algoritmos y el más eficiente, simplemente me gustan los cubos de rubik y los colecciono (más de 40 tipos diferentes de todo el mundo).
maple_shaft
Aunque la respuesta de dasblinknenlight es la solución más simple, le otorgo la recompensa porque me gusta el hecho de que su respuesta incluye parte de la lógica que sería necesaria para dicha estructura de datos y los diferentes atributos de bloque
Rachel
Este modelo de datos es más fiel a la realidad, pero hace que algunas de las operaciones simples que le gustaría hacer sean más difíciles de lo que deberían ser: solo obtener el estado del cubo requeriría viajar recursivamente a través de listas de cubos que es engorroso.
Ziv
@Ziv Cierto, sin embargo, la pregunta era sobre la estructura de datos y no necesariamente sobre los algoritmos.
maple_shaft
13

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.

Matthew Vines
fuente
1
¡Clásico consejo de "no quieres comenzar desde aquí"!
Ergwun
8

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.
usuario156217
fuente
3
Descubrí que este tipo de implementación funciona mejor para representar el cubo en un programa de gráficos 3D. La multiplicación de la matriz hace posible animar las rotaciones de capa. Consulte este repositorio de Github para ver un ejemplo de implementación de este enfoque. Estoy considerando que para agregar un solucionador a mi cubo 3D, necesitaré un algoritmo y una estructura de datos de una de las otras respuestas.
Jonathan Wilson el
5

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

monstruo de trinquete
fuente
1
the most straightforward way of know whether a cube is solvable is to solve it. Bueno, usando el modelo que sugieres, supongo que es cierto. Pero si usa un modelo más cercano a @ maple_shaft's y realiza un seguimiento de las rotaciones, puede probar rápidamente si un cubo de 3x3x3 es solucionable verificando que la suma de los cambios de aristas mod 2 es 0 y las rotaciones de esquina mod 3 es 0. Luego verifique la paridad de la permutación por contando los intercambios de aristas y los intercambios de esquina (necesarios para volver a resolverse), su suma mod 2 debe ser 0 (paridad total incluso). Estas son las pruebas necesarias y suficientes para demostrar que el cubo tiene solución.
jimhark
3

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).

Angelo
fuente
1
Para el punto 2, en lugar de comenzar con un cubo aleatorio y verificar si tiene solución. Comenzaría con un cubo resuelto y realizaría n acciones aleatorias en el cubo para ponerlo en un estado aleatorio.
Matthew Vines
Sí, absolutamente, esa es la forma más simple de generar una configuración que es físicamente posible de resolver. Comenzar con una configuración arbitraria y determinar si es solucionable es definitivamente un problema separado pero relacionado.
Angelo
2
Usted conjetura que podría haber "técnicas sofisticadas" para determinar si un cubo es uno que puede resolverse; de hecho los hay. Si desarma un cubo pero mantiene las calcomanías puestas y luego vuelve a armar el cubo, no necesariamente obtendrá un cubo que tenga solución; de hecho, las probabilidades son de uno a doce en contra de que tengas un cubo solucionable. Puede determinar si está en un estado solucionable mediante un análisis de paridad de los bordes y esquinas; en realidad no tienes que intentar resolver el cubo.
Eric Lippert
1
Aquí hay una breve descripción de los tres tipos de propiedades de paridad de cubo que se deben preservar para que el cubo tenga solución. ryanheise.com/cube/cube_laws.html .
Eric Lippert
1
Publiqué esa pregunta en el sitio de stackexchange del partido y obtuve respuestas realmente agradables: math.stackexchange.com/questions/127577/…
Mel
3

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: La biblioteca de diagramas-rubiks-cube en acción

Ingo Blechschmidt
fuente
2

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.

B Seven
fuente
¡Puedes comprar un cubo de 17x17 ! Tiene algunos compromisos mecánicos, pero es isomorfo a lo real.
RBerteig
1

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.

9000
fuente
1

¿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.

Spencer Rathbun
fuente
-1

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.

martyn fuerte
fuente
Esto no parece ofrecer nada sustancial sobre los puntos hechos y explicados en las 11 respuestas anteriores
mosquito