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

Question

¿Cómo puedo determinar si un determinado Cubo de Rubik que se encuentra en un determinado estado, es solucionable? Por "cierto estado" podría significar que el cubo ha sido desmontado y vuelto a juntar. Y en mi experiencia, si no lo montas de la manera correcta, el cubo podría no ser solucionable.

Una forma de comprobar si hay un cubo de 3x3x3 sería genial. Para cualquier tamaño de cubo, ¡impresionante!

Answer 1

Para un cubo de 3×3×3 hay tres condiciones diferentes que comprobar, normalmente descompuestas como "paridad de permutación", "paridad de arista" y "paridad de esquina".

(Matemáticamente, el grupo que describe todas las formas de desmontar y volver a montar el cubo tiene como subgrupo normal el grupo de los movimientos legales, y el grupo cociente es $C_2\times C_2\times C_3$ Por lo tanto, es natural agrupar la comprobación en tres partes. En principio, debería haber formas equivalentes de tratar el $C_2\times C_2$ pero las paridades globales y de borde son tan naturales que buscar las otras descomposiciones no parece valer la pena).

Imaginamos que los ejes de los husos (y por 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 las configuraciones. En este paso, ignora hacia qué lado se gira cada uno de los cubitos y sólo mira donde ha terminado. De este modo, cada forma de montar el cubo corresponde a alguna permutación particular de los 20 cubos no centrales. Cada permutación legal es una incluso permutación (porque cada cuarto de vuelta es un producto de dos 4 ciclos y, por tanto, es par). Por otro lado, es bien sabido que se puede conseguir cualquier permutación par, siempre que no se intente intercambiar aristas con esquinas.

Para comprobar si una permutación dada es par, basta con escribir la permutación (es decir, la función de "donde el cubo es " a "donde se debe ser") y calcular su signo por cualquier método estándar, por ejemplo, contando las inversiones o desentrañando su estructura de ciclo.

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

Paridad de esquina : Esto rechaza 1/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á junto a un $X$ centro. (Esto trata el $X$ par de colores especialmente; el $Y$ y $Z$ Los lados pueden o no estar alineados con los centros coincidentes). Ahora, para cualquier forma de ensamblar el cubo, considera cuántos en el sentido de las agujas del reloj giros de 120° de una esquina en el lugar que se necesitaría 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 sólo es un poco más complejo que un cuarto de vuelta de $Y$ o $Z$ lo cambia por un múltiplo de $3$ ).

Paridad de bordes : Rechaza la mitad de las configuraciones. Se puede calcular de la misma manera que la paridad de esquina, excepto que la definición de "orientación correcta" para una arista 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á junto a un $X$ centro o si el borde está en la capa media y se orientaría correctamente con un cuarto de vuelta de la $Y$ (pero no $Z$ ) la cara en la que se encuentra.

• A $YZ$ el borde está orientado correctamente o bien si se encuentra entre un $Y$ y un $Z$ centro de la manera obviamente coincidente, o si su $Z$ lado está junto a un $X$ centro.

Ahora se puede comprobar que un cuarto de vuelta de un $X$ o $Y$ cara no cambia si alguna arista está orientada correctamente o no, mientras que una $Z$ un cuarto de vuelta cambia cada uno de los cuatro bordes que mueve de correcto a no correcto o viceversa. Así, cada movimiento legal cambia el número de aristas correctamente orientadas en una cantidad par. Así que debemos rechazar cualquier forma de montar el cubo que acabe con un impar número de aristas mal orientadas.

Aunque no sea inmediatamente obvio, estas tres pruebas rechazarán cualquier configuración que no pueda ser resuelta.

---

La comprobación de la paridad de las esquinas se traslada a los cubos más grandes sin cambios, pero las otras dos pruebas no siempre pueden aplicarse directamente a los cubos más grandes. Para un cubo de 4×4×4 con piezas centrales indistintas, la comprobación de la paridad de las esquinas es la sólo de verificación; cualquier cosa que la satisfaga puede ser resuelta. Para un cubo de 5×5×5, el 3×3×3 virtual formado por las esquinas, los centros centrales y las aristas centrales debe poder resolverse según las reglas del 3×3×3, y resulta que las piezas restantes siempre pueden resolverse, suponiendo de nuevo que los centros son indistintos. I piense en que los cubos más grandes continúan el patrón de 4×4×4 y 5×5×5.

Hay comprobaciones especiales de paridad que se aplican a los supercubos (en los que importa la orientación y/o permutación de las piezas centrales del mismo color principal); no recuerdo de memoria cómo funcionan.

Answer 2

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

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

Para la invariante de la orientación de los bordes, asigne 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 están. Si sacas una pieza de borde y la insertas al revés, cambias el invariante. Por otro lado, si giras una arista (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 una pieza girada en $2\pi$ por lo que esta operación no cambia el invariante. Por supuesto, querrás elegir una asignación que sea fácil de manejar sistemáticamente en un ordenador, pero cualquier asignación servirá.

Asimismo, para el invariante de la orientación de las esquinas, 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 y a las tres caras de cada pieza de esquina; entonces el invariante es el elemento de $\mathbb Z_3$ que se obtiene al sumar 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, esta invariante cambia si se saca una pieza de esquina y se inserta con otra orientación, pero no cambia si se gira un lado.

La 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 se intercambian dos piezas de esquina o dos piezas de borde cualesquiera, se cambia la paridad; en cambio, si se gira un lado, se aplica 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 global no cambia.