¿Cómo saber si un cubo de Rubik tiene solución?

Para un cubo de 3 × 3 × 3, hay tres condiciones diferentes para verificar, generalmente descompuestas como "paridad de permutación", "paridad de borde" y "paridad de esquina".

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

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

Paridad de permutación : Esto rechaza la mitad de todas las configuraciones. En este paso, ignora en qué dirección se gira cada uno de los cubitos y solo mira dónde ha terminado. De esta forma, cada manera 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 producto de dos 4 ciclos y, por lo tanto, es par). Por otro lado, es bien sabido que se puede lograr cualquier permutación uniforme, siempre que no intente intercambiar bordes con esquinas.

Para verificar si una permutación dada es par, simplemente escriba la permutación (es decir, la función desde "dónde está el cubo " hasta "dónde debería estar") y calcule su signo mediante cualquier método estándar, por ejemplo, contando inversiones o desentrañando su estructura cíclica.

Para la paridad de bordes y esquinas, olvidamos temporalmente la diferencia entre los colores opuestos en el cubo; digamos, llamamos tanto blanco como amarillo.$X$, tanto de verde como de azul$Y$y tanto de rojo como de naranja$Z$.

Paridad de esquina : Esto rechaza 2/3 de todas las configuraciones, y se puede definir de la siguiente manera: Como tenemos colores opuestos unificados, cada esquina tiene los colores$X$,$Y$y$Z$. Digamos que una esquina está "orientada correctamente" para su posición instantánea si su$X$lado está al lado de un$X$centro. (Esto trata el$X$par de colores especialmente; el$Y$y$Z$los lados pueden o no alinearse con centros coincidentes). Ahora, para cualquier forma de ensamblar el cubo, considere cuántos giros de 120 ° en el sentido de las agujas del reloj 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 esquina. (Es fácil ver que un cuarto de vuelta de un$X$cara mantiene este número sin cambios, y solo un poco más complejo que un cuarto de vuelta de$Y$o$Z$lo cambia por un múltiplo de$3$).

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

• Un borde con un$X$lado está orientado correctamente si el$X$lado está al lado de un$X$centro o si el borde está en la capa intermedia y se orienta correctamente por un cuarto de vuelta de la$Y$(pero no$Z$) cara en la que se encuentra.

• A$YZ$borde está orientado correctamente, ya sea si se encuentra entre un$Y$y un$Z$centro en la forma obviamente coincidente, o si su$Z$lado está al lado de un$X$centro.

Ahora se puede comprobar que un cuarto de vuelta de un$X$o$Y$cara no cambia si cualquier borde está orientado correctamente o no, mientras que un$Z$un cuarto de vuelta cambia cada uno de los cuatro bordes que mueve de correcto a incorrecto o viceversa. Por lo tanto, cada movimiento legal cambia el número de bordes orientados correctamente en una cantidad uniforme. Así que debemos rechazar cualquier forma de armar el cubo que termine con un número impar de aristas mal orientadas.

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

La comprobación de paridad de esquinas se traslada 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 4×4×4 con piezas centrales indistinguibles, la verificación de paridad de las esquinas es la única verificación; cualquier cosa que la satisfaga puede ser resuelta. Para un cubo de 5×5×5, el 3×3×3 virtual formado por esquinas, centros medios y bordes medios debe ser resoluble de acuerdo con las reglas de 3×3×3, y resulta que las piezas restantes siempre se pueden resolver , suponiendo nuevamente que los centros son indistinguibles. Creo que los cubos más grandes siguen el patrón de 4×4×4 y 5×5×5 .

Hay comprobaciones de paridad especiales para aplicar a los supercubos (donde importa la orientación y/o permutación de las piezas centrales del mismo color principal); No recuerdo de antemano cómo funcionan.

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

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

Para el invariante de la orientación del borde, asigne arbitrariamente los elementos de$\mathbb Z_2$a las dos caras de cada ranura de borde ya 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 saca una pieza de borde y la inserta al revés, cambia 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 por girar una pieza$2\pi$, por lo que esta operación no cambia el invariante. Por supuesto, querrá elegir una tarea que sea fácil de manejar sistemáticamente en una computadora, pero cualquier tarea servirá.

Asimismo, para el invariante de la orientación de la esquina, asigne arbitrariamente los elementos de$\mathbb Z_3$, digamos, en el sentido de las agujas del reloj, a las tres caras de cada ranura de esquina ya las tres caras de cada pieza de esquina; entonces el invariante es el elemento de$\mathbb Z_3$que se obtiene sumando todas las diferencias (en$\mathbb Z_3$) entre las asignaciones de las piezas de las esquinas y las asignaciones de las ranuras de las esquinas en las que se encuentran. Por razones análogas a las anteriores, esta invariante cambia si saca una pieza de la esquina y la inserta con otra orientación, pero no cambia si dar la vuelta a un lado.

El invariante posicional es solo 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 intercambia dos piezas de esquina o dos piezas de borde, cambia la paridad; en cambio, si volteas un lado, aplicas un$4$-ciclo a las piezas de borde y un$4$-ciclo a las piezas de la esquina, por lo que la paridad de la permutación general no cambia.