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 desmontar y reensamblar el cubo tiene el grupo de movimientos legales como un subgrupo normal, y el grupo del cociente es $ C_2 veces C_2 veces C_3 $, por lo que es natural agrupar las verifique en tres partes. En principio, debería haber formas equivalentes de lidiar con el factor $ C_2 times C_2 $, pero las paridades general y de borde 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 ignorable.
Paridad de permutación: Esto rechaza la mitad de todas las configuraciones. En este paso, ignore en qué dirección se gira cada uno de los pequeños cubos y mire 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 incluso permutación (porque cada cuarto de vuelta es un producto de dos 4 ciclos y, por lo tanto, es uniforme). Por otro lado, es bien sabido que se puede lograr cualquier permutación uniforme, siempre que no intente intercambiar bordes con esquinas.
Para comprobar si una permutación dada es par, simplemente escriba la permutación (es decir, la función de “donde el cubo es“a” donde está debería ser “) y calcular su signo mediante cualquier método estándar, por ejemplo, contando 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, llamamos tanto al blanco como al amarillo $ X $, al verde y al azul $ Y $ y al rojo y al 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 lado $ X $ está al lado de un centro $ X $. (Esto trata especialmente al par de colores $ X $; los lados $ Y $ y $ Z $ pueden o no alinearse con los centros coincidentes). Ahora, para cualquier forma de ensamblar el cubo, considere cuántos agujas del reloj Se necesitarían giros de 120 ° de una esquina en su lugar 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 una cara de $ X $ mantiene este número sin cambios, y solo un poco más complejo que un cuarto de vuelta de $ Y $ o $ Z $ lo cambia en 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 esquina, excepto que la definición de “orientación correcta” para un borde es un poco más complicada. Uno puede tomar, por ejemplo:
-
Una arista con un lado $ X $ está orientada correctamente si el lado $ X $ está al lado de un centro $ X $ o si el borde está en la capa media y se orientará correctamente en un cuarto de vuelta de la cara $ Y $ (pero no $ Z $) en la que se encuentra.
-
Un borde $ YZ $ está orientado correctamente cualquiera si se encuentra entre un centro de $ Y $ y un $ Z $ de la manera obviamente coincidente, o si su lado $ Z $ está al lado de un centro $ X $.
Ahora se puede comprobar que un cuarto de vuelta de una cara $ X $ o $ Y $ no cambia si algún borde está orientado correctamente o no, mientras que un cuarto de vuelta de $ Z $ 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 correctamente orientados en una cantidad uniforme. Entonces debemos rechazar cualquier forma de ensamblar el cubo que termine con un impar número de bordes orientados incorrectamente.
Aunque no es obvio de inmediato, estas tres pruebas rechazarán cualquier configuración que no se pueda resolver.
La comprobación de paridad de esquina 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 esquina es la solamente cheque; cualquier cosa que la satisfaga se puede resolver. Para un cubo de 5 × 5 × 5, el 3 × 3 × 3 virtual formado por esquinas, centros medios y aristas medias debe poder resolverse según las reglas del 3 × 3 × 3, y resulta que las piezas restantes siempre se pueden resolver , asumiendo nuevamente que los centros son indistinguibles. I pensar que los cubos más grandes continúan el patrón de 4 × 4 × 4 y 5 × 5 × 5.
Hay controles de paridad especiales para solicitar supercubos (donde la orientación y / o permutación de piezas centrales del mismo color principal es importante); No recuerdo cómo funcionan.
Como se explica en Wikipedia, las operaciones que puede realizar sin desmontar el cubo conducen a clases de equivalencia diferentes de $ 12 $; desea 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 discutió en los comentarios en 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 la orientación de borde invariante, 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 gira un lado (la única operación que puede realizar sin desmontar el cubo), la suma de los cuatro cambios que induce es el cambio que obtendría si una pieza girara $ 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 orientación de 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. razones como las anteriores, este invariante cambia si saca una pieza de esquina y la inserta con otra orientación, pero no cambia si gira 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 cualesquiera o dos piezas de borde, cambia la paridad; por otro lado, si gira un lado, aplica un ciclo de $ 4 $ a las piezas del borde y un ciclo de $ 4 $ a las piezas de las esquinas, por lo que la paridad de la permutación general no cambia.