¿Cómo saber si un cubo de Rubik es resoluble?

Question

¿Cómo puedo determinar si un cubo de Rubik en cierto estado es resoluble? Por "cierto estado" podría significar que el cubo ha sido desarmado y vuelto a armar. Y en mi experiencia, si no lo armas de la manera correcta, es posible que el cubo no sea resoluble.

Sería genial encontrar una manera de comprobar un cubo de $3 \times 3 \times 3$. ¡Para cualquier tamaño de cubo, fenomenal!

Answer 1

Para un cubo de 3x3x3 hay tres condiciones diferentes que verificar, generalmente descompuestas como "paridad de permutación", "paridad de aristas" y "paridad de esquinas".

(Matemáticamente, el grupo que describe todas las formas de desarmar y volver a armar el cubo tiene al grupo de movimientos legales como un subgrupo normal, y el grupo cociente es $C_2\times C_2\times C_3$, por lo que es natural agrupar la verificación en tres partes. En principio debería haber formas equivalentes de tratar el factor $C_2\times C_2$, pero las paridades general y de aristas son tan naturales que buscar las otras descomposiciones no parece valer la pena).

Imaginamos que los ejes del husillo (y por lo tanto los cubos centrales) permanecen fijos en el espacio -- girar todo el cubo es trivial e ignorado.

Paridad de permutación: Esto rechaza 1/2 de todas las configuraciones. En este paso, ignore en qué dirección está girado cada uno de los cubitos y simplemente observe dónde ha terminado. De esta manera, cada forma de ensamblar el cubo corresponde a alguna permutación particular de los 20 cubos no centrales. Cada permutación legal es una permutación par (porque cada cuarto de vuelta es un producto de dos 4-ciclos y por lo tanto en sí misma par). Por otro lado, es bien sabido que cualquier permutación par se puede lograr, siempre y cuando no intente intercambiar aristas con esquinas.

Para verificar si una permutación dada es par, simplemente escriba la permutación (es decir, la función de "dónde está el cubito ahora" a "dónde debería estar") y calcule su signo por cualquier método estándar -- por ejemplo, contando inversiones o desenrollando su estructura de ciclos.

Para la paridad de aristas y esquinas, temporariamente olvidamos la diferencia entre colores opuestos en el cubo -- digamos, llamamos tanto a blanco como amarillo $X$, tanto verde como azul $Y" y tanto rojo como naranja $Z$.

Paridad de esquinas: Esto rechaza 2/3 de todas las configuraciones, y se puede definir de la siguiente manera: Dado que hemos unificado los colores opuestos, cada esquina tiene los colores $X, Y$ y $Z$. Digamos que una esquina está "orientada correctamente" para su posición actual si su lado $X$ está junto a un centro de $X$. (Esto trata a la pareja de colores $X$ de manera especial; los lados $Y$ y $Z$ pueden o no alinearse con centros coincidentes). Ahora, para cualquier forma de ensamblar el cubo, considere cuántas vueltas en sentido de las agujas del reloj de 120° de una esquina en su lugar se necesitarían para orientar todas las esquinas "correctamente" sin moverlas. Si este número es un múltiplo de $3$, la configuración pasa la prueba de paridad de esquinas. (Es fácil ver que un cuarto de giro de una cara $X$ mantiene este número inalterado, y solo un poco más complejo que un cuarto de giro de una cara $Y$ o $Z$ lo cambia por un múltiplo de $3$).

Paridad de aristas: Esto rechaza 1/2 de todas las configuraciones. Se puede calcular de la misma manera que la paridad de esquinas, excepto que la definición de "orientación correcta" para una arista es un poco más complicada. Se puede tomar, por ejemplo:

• Una arista con un lado $X$ está orientada correctamente si el lado $X$ está junto a un centro de $X$ o si la arista está en la capa media y se volvería orientada correctamente con un cuarto de giro de la cara $Y$ (pero no $Z$) en la que se encuentra.

• Una arista $YZ$ está orientada correctamente ya sea si está entre un centro $Y$ y un centro $Z$ de la manera obviamente coincidente, o si su lado $Z$ está junto a un centro $X$.

Ahora se puede comprobar que un cuarto de giro de una cara $X$ o $Y” no altera si alguna arista está orientada correctamente o no, mientras que un cuarto de giro de $Z$ cambia cada una de las cuatro aristas que mueve de correctas a incorrectas o viceversa. Así, cada movimiento legal cambia la cantidad de aristas orientadas correctamente por una cantidad par. Por lo tanto, debemos rechazar cualquier forma de ensamblar el cubo que termine con un número impar de aristas incorrectamente orientadas.

Aunque no es inmediatamente obvio, estas tres pruebas rechazarán cualquier configuración que no se pueda resolver.

---

La prueba de paridad de esquinas se extiende a cubos más grandes sin cambios, pero las otras dos pruebas no siempre se pueden aplicar directamente a cubos más grandes. Para un cubo de 4x4x4 con piezas centrales indistinguibles, la prueba de paridad de esquinas es la única prueba; cualquier cosa que la satisfaga puede ser resuelta. Para un cubo de 5x5x5, el 3x3x3 virtual formado por esquinas, centros medios y aristas medias debe ser resoluble de acuerdo con las reglas de 3x3x3, y resulta que las piezas restantes siempre se pueden resolver, nuevamente asumiendo que los centros son indistinguibles. Creo que los cubos más grandes continúan el patrón desde 4x4x4 y 5x5x5.

Existen pruebas de paridad especiales para supercubos (donde la orientación y/o permutación de las piezas centrales del mismo color principal importa); no recuerdo de memoria cómo funcionan.

Answer 2

Como se explica en Wikipedia, las operaciones que puedes realizar sin desmontar el cubo conducen a $12$ clases de equivalencia diferentes; quieres saber si el estado actual del cubo está en la misma clase que el estado resuelto. Una forma de hacerlo es usar invariantes que caracterizan las clases.

Como se discutió en los comentarios bajo la respuesta del ejemplo (ahora eliminada), los invariantes se descomponen en un invariante de orientación de borde $\mathbb Z_2$, un invariante de orientación de esquina $\mathbb Z_3$ y un invariante posicional $\mathbb Z_2$.

Para el invariante de orientación de borde, asigna arbitrariamente los elementos de $\mathbb Z_2$ a las dos caras de cada ranura de borde y a las dos caras de cada pieza de borde; entonces el invariante es la paridad del número de coincidencias entre las asignaciones de las piezas de borde y las asignaciones de las ranuras de borde en las que se encuentran. Si sacas una pieza de borde y la insertas al revés, cambias el invariante. Por otro lado, si giras un lado (la única operación que puedes realizar sin desmontar el cubo), la suma de los cuatro cambios que induces es el cambio que obtendrías si una pieza se girara $2\pi$ alrededor, por lo que esta operación no cambia el invariante. Por supuesto, querrás elegir una asignación que sea fácil de manejar de forma sistemática en una computadora, pero cualquier asignación servirá.

Del mismo modo, para el invariante de orientación de esquina, asigna arbitrariamente los elementos de $\mathbb Z_3$, digamos, en sentido horario, a las tres caras de cada ranura de esquina y a las tres caras de cada pieza de esquina; entonces el invariante es el elemento de $\mathbb Z_3$ que obtienes sumando todas las diferencias (en $\mathbb Z_3$) entre las asignaciones de las piezas de esquina y las asignaciones de las ranuras de esquina en las que se encuentran. Por razones análogas a las anteriores, este invariante cambia si sacas una pieza de esquina e la insertas con otra orientación, pero no cambia si giras un lado.

El invariante posicional es simplemente la paridad de la permutación de todas las piezas, piezas de borde y piezas de esquina juntas, sin tener en cuenta la orientación. Si intercambias dos piezas de esquina o dos piezas de borde, cambias la paridad; por otro lado, si giras un lado, aplicas un ciclo de $4$ a las piezas de borde y un ciclo de $4$ a las piezas de esquina, por lo que la paridad de la permutación general no cambia.