Solución:
Aquí hay una solución práctica basada en la teoría de grupos elemental que se puede utilizar para resolver muchos acertijos de permutación.
En muchos rompecabezas, hay dos propiedades para cada pieza. Tiene una posición y tiene una orientación. Una pieza puede estar en la posición correcta pero con una orientación incorrecta. Más adelante, cuando me refiero a permutaciones como ciclos, se refiere a las permutaciones de posiciones. Suele darse el caso de que se pueda lograr la misma permutación de piezas con diferentes orientaciones resultantes.
El primer ingrediente se llama conmutador. Un conmutador es cualquier secuencia de movimientos de la forma $ ABA ^ – 1 B ^ – 1 $ donde $ A, B $ son una secuencia de movimientos. $ X ^ – 1 $ denota la inversa de $ X $ como de costumbre. La mayoría de los conmutadores son inútiles para la solución práctica de un rompecabezas. Pero si encuentra $ A, B $ tal que solo hay una posición en la que ambos afectarán la pieza allí si se ejecuta, entonces $ ABA ^ – 1 B ^ – 1 $ afectará las piezas exactamente Solo 2 o 3 posiciones, independientemente de lo complicado que sea cada uno de $ A, B $. Si afecta a 2 posiciones, solo cambiarán las orientaciones de esas piezas. Si afecta a 3 posiciones, esas piezas se permutarán en un ciclo de 3. Puede probar fácilmente este hecho analizando lo que sucede con todas las piezas. Depende de usted descubrir cómo construir y utilizar dichos conmutadores para crear secuencias útiles. Para la mayoría de los rompecabezas, se pueden construir suficientes 3 ciclos para permitir que se realicen todas las permutaciones alternas.
El segundo ingrediente se llama conjugado. Un conjugado es una secuencia de movimientos de la forma $ ABA ^ – 1 $ para algunas secuencias de movimientos $ A, B $. $ ABA ^ – 1 $ hará exactamente lo que hace $ B $ pero en un conjunto diferente de posiciones. Un conjugado es útil cuando podemos usar algunos movimientos $ A $ para ‘configurar’ 3 piezas en algunas posiciones donde se puede usar un conmutador de 3 ciclos para permutarlas de la manera deseada de modo que cuando la ‘configuración’ se deshaga mediante $ A ^ – 1 $ las 3 piezas volverán a sus posiciones originales pero permutadas entre esas posiciones.
El tercer ingrediente se llama paridad. El uso de conmutadores no puede resolver todos los estados posibles de los acertijos de permutación. Esto se debe a que cada conmutador es una permutación uniforme, por lo que es imposible intercambiar solo dos piezas utilizando solo conmutadores. Además, dado que la mayoría de los rompecabezas tienen piezas de diferentes tipos, y cada pieza solo se puede mover a una posición que sea del mismo tipo, significa que para cada tipo puede haber un problema de paridad, lo que significa que es imposible colocar todas las piezas de ese tipo en sus posiciones correctas utilizando sólo 3 ciclos. El número de problemas de paridad será, por supuesto, como máximo el número de tipos de piezas, y es fácil determinar rápidamente si existe un problema de paridad para cualquier tipo dado contando el número de ciclos pares en esas piezas (equivalente a encontrar el signo de la permutación).
Entonces, la receta general para una solución matemática a los acertijos de permutación es:
-
Identifique y solucione todos los problemas de paridad. Por lo general, esto se puede hacer de una pieza a la vez, cada una de las cuales generalmente requiere muy pocos movimientos. Por ejemplo, para el cubo de Rubik de $ 5 times 5 times 5 $ hay 2 paridades (1 para las piezas de las esquinas y los bordes centrales, 1 para los bordes laterales) y cada una de ellas requiere solo 1 movimiento para arreglar (cara un cuarto de vuelta para la primera, rebanada cuarto de vuelta para el segundo, porque cada uno de estos hace un 4 ciclos sobre las piezas de los tipos correspondientes).
-
Una vez que se solucionan todos los problemas de paridad, generalmente es fácil colocar todas las piezas en las posiciones correctas usando conmutadores de 3 ciclos con la ayuda de conjugados, y luego corregir las orientaciones de las piezas usando conmutadores de 2 posiciones (con conjugados). Para acelerar la solución, se debe intentar realizar 3 ciclos de manera que las piezas terminen no solo en las ubicaciones deseadas sino con las orientaciones correctas. Entonces, en general, uno hace cada 3 ciclos para mover 2 piezas a la posición y orientación correctas, mientras que el tercero se ignora. A veces, solo se puede liquidar 1 pieza (cuando solo hay permutas). De cualquier manera, el número de piezas en la posición incorrecta disminuirá con cada 3 ciclos hasta que todas estén en las posiciones correctas. Este hecho de la alternancia de grupos se puede probar muy fácilmente. Para un cubo de Rubik, se necesitan de 8 a 10 movimientos (contando el turno de corte como 1 movimiento) para hacer la mayoría de los 3 ciclos, incluida la obtención de las orientaciones deseadas para 2 piezas.
En el caso de rompecabezas en los que algunos movimientos pueden bloquearse físicamente dependiendo del estado del rompecabezas (como el Cuadrado-1), puede ser una buena idea poner el rompecabezas en un estado agradable (es decir, un elemento de algún subgrupo agradable) y desarrollar una solución basada en lo anterior solo para estados agradables. No tengo un Square-1, así que no sé qué tan fácil es resolverlo de esta manera.
El método anterior funciona muy bien para un cubo de Rubik de cualquier tamaño, así como para acertijos de permutación que están estrechamente relacionados con el cubo de Rubik. Básicamente, los rompecabezas donde los conmutadores de 3 ciclos son fáciles de construir no son un desafío. Hay algunos rompecabezas desagradables como Tatham’s Twiddle (bloques giratorios 4×4) donde es difícil encontrar conmutadores de 3 ciclos. Generalmente, mi estrategia para abordar este tipo de acertijos sería encontrar conmutadores que afecten a pocas piezas y componerlas de manera que afecten cada vez a menos piezas. Eventualmente encontraría un conmutador de 3 ciclos (a menos que no haya ninguno), y luego puedo resolver el rompecabezas usando conjugados para llevar otras piezas a las posiciones en las que funciona el conmutador para que puedan permutarse. Es posible que los problemas de paridad hagan que un solo conmutador sea insuficiente, por lo que aún es necesario un análisis ad-hoc.
Método específico para el $ boldsymbol n times n times n cubo de $ Rubik y parientes cercanos
El primer paso es encontrar conmutadores de 3 ciclos. Para el cubo de Rubik, los conmutadores más fáciles $ ABA ^ – 1 B ^ – 1 $ son donde $ B $ es un giro de una sola cara / corte y $ A $ es una secuencia de movimientos que cambia solo una pieza en esa cara /rodaja. $ A, B $ se pueden elegir fácilmente para muchos de los 3 ciclos deseados de la siguiente manera. Dada una pieza $ x $ que se puede colocar en su lugar, incluida la orientación en un solo giro de cara / corte, elija cualquier $ A $ que cambie $ x $ de esa cara / corte $ S $. Es fácil ver que, después de hacer $ A $, puede hacer que una sola cara / corte gire $ B $ de modo que, cuando deshaga $ A $, $ x $ iría al lugar correcto con respecto a $ S $, y luego, después de deshacer $ B $, $ x $ estaría en el lugar correcto con respecto al cubo completo. Dado que la posición original de $ x $ ahora estaría ocupada por alguna pieza que fue desplazada allí por $ A $, significa que si eliges $ A $ con cuidado puedes tirar de la pieza correcta (la que pertenece a la posición original de $ x $) con la orientación correcta mientras empuja $ x $ fuera de $ S $, siempre que la pieza correcta originalmente no estuviera en $ S $. Si no es así, simplemente extraiga alguna pieza sin resolver.
Si no hay piezas que puedan colocarse en su lugar con un solo giro de cara / rebanada, aquí es donde entran los conjugados. Si queremos mover una pieza $ x $ a la posición $ p $, busque una secuencia de movimientos $ C $ eso no cambia la pieza actualmente en $ p $, pero cambia $ x $ a una posición desde la cual se puede cambiar a $ p $ con la orientación correcta en una cara / corte. Entonces, ahora se pueden realizar conmutadores de 3 ciclos que cambian $ x $ a $ p $ como se describió anteriormente. Finalmente deshacemos $ C $. No es difícil ver que $ C $ es solo un cambio de perspectiva, por lo que toda la secuencia $ CABA ^ – 1 B ^ – 1 C ^ – 1 $ también es un ciclo de 3. Con un poco de práctica, es fácil rastrear mentalmente el cambio de perspectiva para que podamos elegir el $ A $ apropiado para extraer la pieza correcta que iría al lugar correcto con respecto a la perspectiva cambiada, de modo que sería en el lugar correcto después de deshacer $ C $.
Con estos 3 ciclos puede resolver 2 piezas (incluida la orientación) a la vez, a menos que todas las piezas sin resolver estén en 2 ciclos o estén en la posición correcta pero en la orientación incorrecta. Si todavía hay 2 ciclos, solo resuelve 1 pieza a la vez. Si cada pieza sin resolver está mal orientada, puede estropearlas y volver a colocarlas correctamente usando 3 ciclos, o puede usar los conmutadores de 2 ciclos.
Un conmutador de 2 ciclos $ ABA ^ – 1 B ^ – 1 $ que orienta las piezas $ x, y $ que están ambas en la misma cara / corte $ S $ se puede encontrar de la siguiente manera. Elija $ A $ para que sea una secuencia de movimientos que oriente $ x $ correctamente pero no cambie ninguna otra pieza en $ S $. Entonces está claro que si haces $ A $ y luego una sola cara / rebanada gira $ B $ para llevar $ y $ a la posición de $ x $, entonces deshacer $ A $ realizaría la orientación opuesta a $ y $ que volvería a su posición original después de deshacer $ B $. Junto con un conjugado, esto nos permite torcer dos piezas del mismo tipo al mismo tiempo “en direcciones opuestas”.
Una vez que se sienta cómodo con los conmutadores anteriores, puede extender fácilmente la idea a 3 ciclos de grupos de piezas, como pares o bloques más grandes. Estos no son útiles para resolver un cubo de Rubik desde un estado aleatorio, pero son muy útiles cuando se crean patrones a partir del estado resuelto.
Método eficiente para el $ boldsymbol 3 times 3 times 3 $ cubo de Rubik
El método anterior funciona con cubos de Rubik de cualquier tamaño, así como con rompecabezas estrechamente relacionados, pero, por supuesto, la estructura del cubo produce métodos más eficientes. Aquí hay uno simple que todavía se basa en parte en la teoría de grupos, pero bastante ad-hoc, aunque todo tiene sentido y, por lo tanto, no requiere ningún trabajo de memoria.
Primero resuelve los bordes inferiores. Luego resuelve 3 de las esquinas inferiores (sin estropear los bordes inferiores). Ahora resuelve 3 de los bordes laterales; para cada uno de ellos, gire la cara inferior de modo que la esquina inferior sin resolver esté por debajo de la posición deseada del borde lateral, y luego sea fácil tirar de la pieza del borde con la orientación correcta sin estropear la cara inferior excepto la esquina sin resolver. Por supuesto, a veces puede ser necesario empujar las piezas del borde lateral hacia la cara superior antes de colocarlas en el lugar correcto. Ahora nos quedan 5 aristas y 5 esquinas.
A continuación orientaremos los 5 bordes. Gire la cara inferior para alinear la esquina inferior sin resolver y el borde lateral, y gire el cubo para que pueda ver las caras a su izquierda y derecha, así como la cara superior. Sean $ L, R, T $ cuartos de vuelta en el sentido de las agujas del reloj de esas caras. Usando solo secuencias de movimiento de la forma $ T ^ kL ^ – 1 T ^ mL $ y $ T ^ kRT ^ mR ^ – 1 $ podrá orientar todos los bordes superiores, lo que significa que cualquier borde superior que esté en la cara superior está orientada con el color superior hacia arriba. Tenga en cuenta que $ L ^ – 1 $ o $ R $ no harán que ningún borde superior tenga una orientación incorrecta. Digamos que es $ R $. Ahora nos restringimos temporalmente a movimientos usando solo $ R, T $; al permanecer en este subgrupo, los bordes mantendrán sus orientaciones correctas.
Luego arreglaremos los problemas de paridad para que podamos terminar con conmutadores de algún tipo. Dado que la paridad del borde está vinculada a la esquina paridad, solo tenemos que determinar la paridad de las piezas de borde. Si es una permutación par (número par de ciclos), entonces no hacemos nada, de lo contrario, simplemente realizamos un $ T $ para igualarlo.
Basado en la orientación de la pieza de borde en la posición del borde lateral, limítese a mover secuencias de la forma $ T ^ kRT ^ – k + m R ^ – 1 T ^ – m $ solamente. Cada uno de ellos es en realidad un conmutador de 3 ciclos (conjugado) en los 5 bordes (simulando que no hay piezas de esquina). Dado que la orientación es automática, necesita como máximo 2 conmutadores para resolver los 5. Además, el uso de estas secuencias asegura que las piezas resueltas anteriormente no se alteren. En la práctica, por supuesto, los $ T $ s entre los conmutadores se cancelarán.
Finalmente podemos volver a girar la cara inferior para poner las piezas en sus lugares adecuados y solo nos quedarán 5 esquinas, por lo que simplemente usamos conmutadores sin ninguna restricción en el tipo de movimientos. Por lo general, se necesitan 2 o 3 conmutadores. Hay formas de optimizar esta parte, pero eso queda para que el lector las descubra.
Tenga en cuenta que a lo largo de este método, el principio subyacente es que dejamos suficientes piezas sin resolver para que podamos resolver otras piezas de manera eficiente. Resulta que, en promedio, este método requiere de 60 a 70 movimientos, lo que es casi tan eficiente como los métodos convencionales basados en la memorización que generalmente involucran más de 50 algoritmos de caja negra, pero brindan una comprensión intuitiva de cada movimiento y con un poco de Practique (y trucos con los dedos) cualquiera que use este método debería poder llegar a menos de 35 segundos de manera constante.
Puedo agregar que si alguien se pregunta sobre el número máximo de 3 ciclos requeridos para resolver / generar cualquier permutación uniforme de cualquier $ n veces n veces n $ órbita de piezas del cubo de Rubik (ignorando las orientaciones de la esquina y del borde medio), obtengo que se necesita un máximo de:
- 12 ciclos de 3 para resolver cada centro no fijo y órbita de borde de ala (uno a la vez).
- El número medio exacto de 3 ciclos necesarios para resolver todos los casos de permutación pares $ 24! / 2 $ de 24 objetos es $ 7272437897/669278610 $ (aproximadamente 10,87).
- Para los bordes medios (12 objetos), se requiere un máximo de 6 3 ciclos.
- El número medio exacto de 3 ciclos para manejar todas las permutaciones pares de $ 12! / 2 $ es 34757/6930, que es aproximadamente 5,02.
- Para esquinas (8 objetos), se requiere un máximo de 4 3 ciclos.
- El número medio exacto de 3 ciclos para manejar las 8! / 2 permutaciones pares es 649/210, que es aproximadamente 3,09.
Todos estos cálculos incluyen el caso resuelto (que obviamente es una permutación par y se incluye en el k! / 2 cantidades).
Para la posible curiosidad de todos, esto significa que se necesita un máximo de este número o un promedio de este número de 3 ciclos para resolver el cubo $ n veces n veces x veces n $. (Simplemente sustituya un número entero que corresponda al tamaño del cubo por k a la derecha de la entrada en Wolfram Alpha).
Es decir, el número máximo de funciones de 3 ciclos para resolver el supercubo $ n times n times n $ (donde ignoramos los giros de los centros fijos en el supercubo $ n times n times n $ impares, y no los centros fijos son único) es simplemente $ 3n ^ 2 – 6n + frac 3 cos left (n pi right) + 5 2 $.
Suponga que usamos 3 ciclos que tienen 10 movimientos de longitud. Esto significa que debería tomar aproximadamente (8) (10) = 80 movimientos para resolver el 3x3x3 en promedio usando este enfoque (donde el estado “resuelto” será uno en el que las esquinas y los bordes centrales probablemente no estén orientados), y aproximadamente (10) (26635) = 266,350 movimientos en promedio para resolver el 100x100x100. Por supuesto, aplicamos en la mayoría de Floor[n/2] cortar un cuarto de vuelta para obtener el norteXnorteXnorte supercubo en el norteXnorteXnorte subgrupo de conmutador supercubo, y por lo tanto agregamos este término a nuestro número total de movimientos estimados.
Claramente, dado que estos cálculos son para el supercubo $ n veces n veces n $, lo más probable es que el número máximo real de 3 ciclos requeridos para resolver el cubo regular de 6 colores $ n veces n veces n $ menos, aunque hacer tal cálculo requeriría una búsqueda de fuerza bruta mucho más complicada que la que hice para estos cálculos de supercubo.
Nos puedes añadir valor a nuestra información añadiendo tu veteranía en las notas.