Soluciones óptimas para el cubo de Rubik

Las soluciones óptimas para el cubo de Rubik se refieren a las soluciones más cortas. Hay dos formas comunes de medir la longitud de una solución. La primera es contar el número de cuartos de vuelta. El segundo es contar el número de giros de la capa exterior, llamados "giros de cara". Un movimiento para girar una capa exterior dos cuartos de vuelta (90 °) en la misma dirección se contabilizaría como dos movimientos en la métrica de cuarto de vuelta (QTM), pero como un giro en la métrica de cara (FTM o HTM "Half Turn Metric", o OBTM" Métrica de giro del bloque exterior"). ^[1]​

Un cubo de Rubik mezclado.

El número mínimo de vueltas de caras necesarias para resolver cualquier instancia del cubo de Rubik es 20,^[2]​ y el número mínimo de cuartos de vuelta es 26.^[3]​ Estos números también son los diámetros de los correspondientes grafos de Cayley del grupo del cubo de Rubik. En STM (métrica de giro de corte) se desconoce.

Hay muchos algoritmos para resolver cubos de Rubik codificados. Un algoritmo que resuelve un cubo en el número mínimo de movimientos se conoce como algoritmo de Dios.

Notación de movimientos

Artículo principal: Cubo de Rubik#Notación

Para denotar una secuencia de movimientos en el cubo de Rubik de 3 × 3 × 3, este artículo utiliza la "notación Singmaster",^[4]​ que fue desarrollada por David Singmaster.

Las letras L, R, F, B, U y D indican un cuarto de vuelta en el sentido de las agujas del reloj de la cara izquierda, derecha, delantera, trasera, arriba y abajo, respectivamente. Las medias vueltas se indican añadiendo un 2. Un cuarto de vuelta en sentido antihorario se indica añadiendo un símbolo de prima (′).

Las letras M, S y E se utilizan para denotar el giro de una capa intermedia. M representa girar la capa entre las caras R y L 1 cuarto de vuelta de arriba abajo. S representa girar la capa entre las caras F y B 1 cuarto de vuelta en el sentido de las agujas del reloj, visto desde el frente. E representa girar la capa entre las caras U y D 1 cuarto de vuelta en el sentido de las agujas del reloj de izquierda a derecha. Al igual que con los giros regulares, un 2 significa un giro doble y un primo (') indica un cuarto de giro en sentido antihorario.^[5]​

Las letras X, Y y Z se utilizan para indicar rotaciones de cubos. X significa la rotación del cubo hacia adelante 90 grados. Y significa la rotación del cubo a la izquierda 90 grados. Z significa la rotación del cubo en el sentido de las agujas del reloj 90 grados. Estas rotaciones de cubos se utilizan en algoritmos para hacer que los algoritmos sean más suaves y rápidos. Al igual que con los giros regulares, un 2 significa media rotación y un primo (') indica un cuarto de rotación en la dirección opuesta. Téngase en cuenta que estas letras suelen estar en minúsculas.

Límites inferiores

Se puede probar contando argumentos que existen posiciones que necesitan al menos 18 movimientos para resolver. Para mostrar esto, primero cuente el número de posiciones de cubos que existen en total, luego cuente el número de posiciones alcanzables usando como máximo 17 movimientos comenzando desde un cubo resuelto. Resulta que este último número es menor.

Este argumento no se mejoró durante muchos años. Además, no es una prueba constructiva: no exhibe una posición concreta que necesite tantos movimientos. Se conjeturaba que el llamado superflip sería una posición muy difícil. Un cubo de Rubik está en el patrón superflip cuando cada pieza de esquina está en la posición correcta, pero cada pieza de borde está orientada incorrectamente. ^[6]​ IEn 1992, Dik T. Winter encontró una solución para el superflip con 20 vueltas de cara, cuya minimidad fue mostrada en 1995 por Michael Reid, proporcionando un nuevo límite inferior para el diámetro del grupo de cubos. También en 1995, Michael Reid encontró una solución para superflip en 24 cuartos de vuelta, con su minimidad probada por Jerry Bryan.^[6]​ En 1998, se encontró una nueva posición que requería más de 24 cuartos de vuelta para resolverse. La posición, que se denominó 'superflip compuesta con cuatro puntos' necesita 26 cuartos de vuelta.^[7]​

Límites superiores

Los primeros límites superiores se basaron en los algoritmos "humanos". Al combinar los escenarios del peor de los casos para cada parte de estos algoritmos, se encontró que el límite superior típico era de alrededor de 100.

Quizás el primer valor concreto para un límite superior fueron los 277 movimientos mencionados por David Singmaster a principios de 1979. Simplemente contó el número máximo de movimientos requeridos por su algoritmo de resolución de cubos.^[8]​^[9]​ Más tarde, Singmaster informó que Elwyn Berlekamp, John Conway, y Richard K. Guy habían ideado un algoritmo diferente que requería como máximo 160 movimientos.^[8]​^[10]​ Poco después, los cubistas de Cambridge de Conway informaron que el cubo podría restaurarse en 94 movimientos como máximo.^[8]​^[11]​

Algoritmo de Thistlethwaite

El avance, conocido como "descenso a través de subgrupos anidados" fue encontrado por Morwen Thistlethwaite; Los detalles del algoritmo de Thistlethwaite fueron publicados en Scientific American en 1981 por Douglas Hofstadter. Las aproximaciones al cubo que llevaron a algoritmos con muy pocos movimientos se basan en la teoría de grupos y en extensas búsquedas por computadora. La idea de Thistlethwaite era dividir el problema en subproblemas. Donde los algoritmos hasta ese punto dividieron el problema al observar las partes del cubo que deberían permanecer fijas, lo dividió restringiendo el tipo de movimientos que podrían ejecutarse. En particular, dividió el grupo de cubos en la siguiente cadena de subgrupos:

• ${\displaystyle G_{0}=\langle L,R,F,B,U,D\rangle }$ 
• ${\displaystyle G_{1}=\langle L,R,F,B,U^{2},D^{2}\rangle }$ 
• ${\displaystyle G_{2}=\langle L,R,F^{2},B^{2},U^{2},D^{2}\rangle }$ 
• ${\displaystyle G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle }$ 
• ${\displaystyle G_{4}=\{1\}}$ 

A continuación, preparó tablas para cada uno de los espacios laterales correctos ${\displaystyle G_{i+1}\setminus G_{i}}$ . Para cada elemento, encontró una secuencia de movimientos que lo llevaron al siguiente grupo más pequeño. Después de estos preparativos trabajó de la siguiente manera. Un cubo aleatorio está en el grupo de cubos general ${\displaystyle G_{0}}$ . A continuación se encontró con este elemento en el espacio de la clase lateral derecha${\displaystyle G_{1}\setminus G_{0}}$ . Aplicó el proceso correspondiente al cubo. Esto lo llevó a un cubo en ${\displaystyle G_{1}}$ . A continuación, buscó un proceso que lleva al cubo a ${\displaystyle G_{2}}$ , cerca de ${\displaystyle G_{3}}$  y finalmente a ${\displaystyle G_{4}}$ .

 

Estado intermedio del cubo de Rubik en el algoritmo de Kociemba. Cualquier estado de G₁ tendrá los símbolos "+" y "-" como se muestra.^[12]​

Aunque todo el grupo de cubos ${\displaystyle G_{0}}$  es muy grande (~4.3×10¹⁹), los espacios laterales de la derecha ${\displaystyle G_{1}\setminus G_{0},G_{2}\setminus G_{1},G_{3}\setminus G_{2}}$  y ${\displaystyle G_{3}}$  son mucho más pequeños. El espacio lateral ${\displaystyle G_{2}\setminus G_{1}}$  es el más grande y contiene solo 1082565 elementos. El número de movimientos requeridos por este algoritmo es la suma del proceso más grande en cada paso.

Inicialmente, Thistlethwaite mostró que cualquier configuración podía resolverse en un máximo de 85 movimientos. En enero de 1980 mejoró su estrategia para producir un máximo de 80 movimientos. Más tarde, ese mismo año, redujo el número a 63, y luego nuevamente a 52.^[8]​ Al buscar exhaustivamente los espacios laterales, se encontró más tarde que el peor número posible de movimientos para cada etapa era 7, 10, 13 y 15. dando un total de 45 movimientos como máximo.^[13]​ Existe una implementación del algoritmo de Thistlewaite en Javascript.^[14]​

Algoritmo de Kociemba

El algoritmo de Thistlethwaite fue mejorado por Herbert Kociemba en 1992. Redujo el número de grupos intermedios a solo dos:

• ${\displaystyle G_{0}=\langle U,D,L,R,F,B\rangle }$ 
• ${\displaystyle G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle }$ 
• ${\displaystyle G_{2}=\{1\}}$ 

Al igual que con el algoritmo de Thistlethwaite , buscaría en el espacio lateral derecho ${\displaystyle G_{1}\setminus G_{0}}$  llevar el cubo al grupo ${\displaystyle G_{1}}$ . A continuación, buscó la solución óptima para el grupo ${\displaystyle G_{1}}$ . Las búsquedas en ${\displaystyle G_{1}\setminus G_{0}}$  y ${\displaystyle G_{1}}$  mbos se realizaron con un método equivalente a IDA*. La búsqueda en ${\displaystyle G_{1}\setminus G_{0}}$  necesita como máximo 12 movimientos y la búsqueda en ${\displaystyle G_{1}}$  como máximo 18 movimientos, como lo demostró Michael Reid en 1995. Al generar también soluciones subóptimas que llevan al cubo a agrupar ${\displaystyle G_{1}}$  y buscando soluciones cortas en ${\displaystyle G_{1}}$ , normalmente se obtienen soluciones globales mucho más cortas. Con este algoritmo, las soluciones se encuentran típicamente en menos de 21 movimientos, aunque no hay pruebas de que siempre lo haga.

En 1995 Michael Reid demostró que utilizando estos dos grupos cada posición se puede resolver en un máximo de 29 vueltas de cara o en 42 cuartos de vuelta. Este resultado fue mejorado por Silviu Radu en 2005 a 40.

A primera vista, este algoritmo parece ser imprácticamente ineficaz, si ${\displaystyle G_{0}}$ contiene 18 movimientos posibles (cada movimiento, su principal y su rotación de 180 grados), que deja ${\displaystyle 18^{12}}$ estados de cubos para buscar. Incluso con un algoritmo informático basado en heurística como IDA*, que puede reducirlo considerablemente, es probable que la búsqueda en tantos estados no sea práctica. Para resolver este problema, Kociemba ideó una tabla de búsqueda que proporciona una heurística exacta para ${\displaystyle G_{0}}$ .^[15]​ Cuando el número exacto de movimientos necesarios para alcanzar ${\displaystyle G_{1}}$ está disponible, la búsqueda se vuelve prácticamente instantánea: solo es necesario generar 18 estados de cubo para cada uno de los 12 movimientos y elegir el que tenga la heurística más baja cada vez. Esto permite la segunda heurística, que para ${\displaystyle G_{1}}$ , para ser menos precisos y aún permitir que una solución se calcule en un tiempo razonable en una computadora moderna.

Algoritmo de Korf

El uso de estas soluciones grupales combinadas con búsquedas por computadora generalmente dará soluciones muy breves. Pero estas soluciones no siempre vienen con garantía de su minimidad. Para buscar específicamente soluciones mínimas se necesitaba un nuevo enfoque.

En 1997, Richard Korf^[16]​ anunció un algoritmo con el que había resuelto de forma óptima instancias aleatorias del cubo. De los diez cubos aleatorios que hizo, ninguno requirió más de 18 vueltas de cara. El método que utilizó se llama IDA* y se describe en su artículo "Encontrar soluciones óptimas para el cubo de Rubik utilizando bases de datos de patrones". Korf describe este método de la siguiente manera

IDA* es una búsqueda en profundidad que busca soluciones cada vez más largas en una serie de iteraciones, utilizando una heurística de límite inferior para podar ramas una vez que un límite inferior en su longitud excede el límite de iteraciones actuales.

Funciona aproximadamente de la siguiente manera. Primero identificó una serie de subproblemas que son lo suficientemente pequeños como para resolverse de manera óptima. El usó:

1. El cubo restringido solo a las esquinas, sin mirar los bordes
2. El cubo se limita a solo 6 bordes, sin mirar las esquinas ni los otros bordes.
3. El cubo restringido a los otros 6 bordes.

Claramente, el número de movimientos necesarios para resolver cualquiera de estos subproblemas es un límite inferior para el número de movimientos necesarios para resolver todo el cubo.

Dado un cubo C aleatorio, se resuelve como profundización iterativa. Primero se generan todos los cubos que son el resultado de aplicarles 1 movimiento. Eso es C * F, C * U,… A continuación, de esta lista, se generan todos los cubos que son el resultado de aplicar dos movimientos. Luego tres movimientos y así sucesivamente. Si en algún momento se encuentra un cubo que necesita demasiados movimientos basados en los límites superiores para seguir siendo óptimo, se puede eliminar de la lista.

Aunque este algoritmo siempre encontrará soluciones óptimas, no existe un análisis del peor de los casos. No se sabe cuántos movimientos podría necesitar este algoritmo. Aquí se puede encontrar una implementación de este algoritmo.^[17]​

Más mejoras y encontrar el número de Dios

En 2006, Silviu Radu mejoró aún más sus métodos para demostrar que cada posición se puede resolver en un máximo de 27 vueltas de cara o 35 cuartos de vuelta.^[18]​ Daniel Kunkle y Gene Cooperman en 2007 usaron una supercomputadora para mostrar que todos los cubos sin resolver se pueden resolver en no más de 26 movimientos (en métrica de giro de caras). En lugar de intentar resolver cada uno de los miles de millones de variaciones de manera explícita, la computadora fue programada para llevar el cubo a uno de los 15.752 estados, cada uno de los cuales podría resolverse con unos pocos movimientos adicionales. Se demostró que todos se resolvían en 29 movimientos, y la mayoría se resolvía en 26. Aquellos que inicialmente no se podían resolver en 26 movimientos se resolvieron luego explícitamente, y se demostró que también se podían resolver en 26 movimientos.^[19]​^[20]​

Tomas Rokicki informó en una prueba computacional de 2008 que todos los cubos sin resolver se podrían resolver en 25 movimientos o menos.^[21]​ Esto luego se redujo a 23 movimientos.^[22]​ En agosto de 2008, Rokicki anunció que tenía una prueba para 22 movimientos.^[23]​

Finalmente, en 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge dieron la prueba final asistida por computadora de que todas las posiciones de los cubos se podían resolver con un máximo de 20 vueltas de caras.^[2]​En 2009, Tomas Rokicki demostró que 29 movimientos en la métrica de un cuarto de turno son suficientes para resolver cualquier cubo revuelto.^[24]​ Y en 2014, Tomas Rokicki y Morley Davidson demostraron que el número máximo de cuartos de vuelta necesarios para resolver el cubo es 26.^[3]​

Las métricas de giro y cuarto de vuelta difieren en la naturaleza de sus antípodas.^[3]​ Una antípoda es un cubo revuelto que está muy lejos de resolverse, uno que requiere el máximo número de movimientos para resolverse. En la métrica de media vuelta con un número máximo de 20, hay cientos de millones de tales posiciones. En la métrica de cuarto de vuelta, solo se conoce una posición (y sus dos rotaciones) que requiere el máximo de 26 movimientos. A pesar de un esfuerzo significativo, no se han encontrado posiciones adicionales de un cuarto de vuelta con distancia 26. Incluso a una distancia de 25, solo se sabe que existen dos posiciones (y sus rotaciones).^[3]​^{[cita requerida]} A la distancia 24, tal vez existan 150.000 posiciones.

Referencias

1. «World Cube Association». www.worldcubeassociation.org. Consultado el 20 de febrero de 2017. 
2. «God's Number is 20». cube20.org. Consultado el 23 de mayo de 2017. 
3. «God's Number is 26 in the Quarter Turn Metric». cube20.org. Consultado el 20 de febrero de 2017. 
4. Joyner, David (2002). Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys. Baltimore: Johns Hopkins University Press. pp. 7. ISBN 0-8018-6947-1. 
5. «Rubik's Cube Notation». Ruwix (en inglés estadounidense). Consultado el 19 de marzo de 2017. 
6. Michael Reid's Rubik's Cube page M-symmetric positions
7. Posted to Cube lovers on 2 Aug 1998
8. Rik van Grol (November 2010). . Math Horizons. Archivado desde el original el 9 de noviembre de 2014. Consultado el 26 de julio de 2013. 
9. Singmaster, 1981, p. 16.
10. Singmaster, 1981, p. 26.
11. Singmaster, 1981, p. 30.
12. Herbert Kociemba. «The Subgroup H and its cosets». Consultado el 28 de julio de 2013. 
13. Progressive Improvements in Solving Algorithms
14. Implementation of Thistlewaite's Algorithm for Rubik's Cube Solution in Javascript
15. «Solve Rubik's Cube with Cube Explorer». kociemba.org. Consultado el 27 de noviembre de 2018. 
16. Richard Korf (1997). «Finding Optimal Solutions to Rubik's Cube Using Pattern Databases». 
17. Michael Reid's Optimal Solver for Rubik's Cube (requires a compiler such as gcc)
18. Rubik can be solved in 27f
19. Press Release on Proof that 26 Face Turns Suffice
20. Kunkle, D.; Cooperman, C. (2007). «Twenty-Six Moves Suffice for Rubik's Cube». Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07). ACM Press. 
21. Tom Rokicki (2008). «Twenty-Five Moves Suffice for Rubik's Cube». arXiv:0803.3435  [cs.SC]. 
22. Twenty-Three Moves Suffice — Domain of the Cube Forum
23. twenty-two moves suffice
24. Tom Rokicki. «Twenty-Nine QTM Moves Suffice». Consultado el 19 de febrero de 2010. 

Lecturas adicionales

• Singmaster, David (1981). Notes on Rubik's Magic Cube. Enslow Publishers. 

Enlaces externos

•   Wikilibros alberga un libro o manual sobre How to solve the Rubik's Cube.