Las soluciones óptimas para el cubo de Rubik son aquellas que son las más cortas en algún sentido. Hay dos formas comunes de medir la longitud de una solución. La primera es contar el número de cuartos de vuelta. La segunda 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 "Metrica de media vuelta", u OBTM "Metrica de giro del bloque exterior"). [1]
El número máximo de vueltas de cara necesarias para resolver cualquier instancia del Cubo de Rubik es 20, [2] y el número máximo de cuartos de vuelta es 26. [3] Estos números son también los diámetros de los gráficos de Cayley correspondientes del grupo del Cubo de Rubik . En STM (métrica de vueltas de rebanada), se desconoce el número mínimo de vueltas.
Existen muchos algoritmos para resolver cubos de Rubik desordenados . El algoritmo que resuelve un cubo en el mínimo número de movimientos se conoce como algoritmo de Dios .
Para denotar una secuencia de movimientos en el Cubo de Rubik 3×3×3, este artículo utiliza la "notación Singmaster", [4] que fue desarrollada por David Singmaster .
Los siguientes son movimientos estándar, que no mueven los cubos centrales de ninguna cara a otra ubicación:
Las letras L , R , F , B , U y D indican un cuarto de giro en el sentido de las agujas del reloj de la cara izquierda, derecha, frontal, posterior, superior e inferior respectivamente. Un medio giro (es decir, 2 cuartos de giro en la misma dirección) se indica añadiendo un 2. Un giro en el sentido contrario a las agujas del reloj se indica añadiendo un símbolo primo (′).
Sin embargo, debido a que estas notaciones están orientadas a los humanos, usamos el sentido de las agujas del reloj como positivo, y no el sentido matemático, que es el sentido contrario a las agujas del reloj como positivo.
Los siguientes son movimientos no estándar
Los movimientos no estándar generalmente se representan con letras minúsculas en contraste con los movimientos estándar mencionados anteriormente.
Mover los cubos centrales de las caras a otras ubicaciones:
Las letras M , S y E se utilizan para indicar el giro de una capa intermedia. M (abreviatura de capa "intermedia") representa girar la capa entre las caras R y L 1 cuarto de vuelta en el sentido de las agujas del reloj (de adelante hacia atrás <- lo has hecho al revés), como se ve de frente a la cara L (invisible). S (abreviatura de capa "de pie") representa girar la capa entre las caras F y B 1 cuarto de vuelta en el sentido de las agujas del reloj (de arriba hacia abajo), como se ve de frente a la cara F (visible). E (abreviatura de capa "ecuador") 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), como se ve de frente a la cara D (invisible). Al igual que con los giros regulares, un 2 significa medio giro y una prima (') indica un giro en el sentido contrario a las agujas del reloj. [5]
Las letras M , S y E están mal definidas, como lo evidencian los paréntesis con "visible" e "invisible".
Las letras H , S y V se utilizan para indicar el giro de una capa intermedia. H (abreviatura de capa "Horizontal") representa girar la capa entre las caras U y D 1 cuarto de vuelta en el sentido de las agujas del reloj, como se ve de frente a la cara U (visible). S (abreviatura de capa "Lateral") representa girar la capa entre las caras F y B 1 cuarto de vuelta en el sentido de las agujas del reloj, como se ve de frente a la cara F (visible). V (abreviatura de capa "Vertical") representa girar la capa entre las caras R y L 1 cuarto de vuelta en el sentido de las agujas del reloj, como se ve de frente a la cara R (visible). Al igual que con los giros regulares, una prima (') indica un giro en el sentido contrario a las agujas del reloj y un 2 significa medio giro. [6]
(Eliminaste el párrafo antiguo que decía que M , S y E están "mal definidas", lo que hacía que la palabra "en cambio" al comienzo del párrafo siguiente con r , f y u pareciera desconectada. En ese momento, no había ningún párrafo sobre H , S y V ).
En cambio, también se utilizan las letras minúsculas r , f y u para indicar capas de giro junto a R , F y U respectivamente en la misma dirección que R , F y U. Esto es más coherente con los cubos de 4 capas. [7]
En cubos de varias capas, los números pueden preceder a los nombres de las caras para indicar la rotación de la capa n a partir de la cara nombrada. 2R , 2F y 2U se utilizan entonces para indicar capas que giran junto a R , F y U respectivamente en la misma dirección que R , F y U. El uso de esta notación para un cubo de tres capas es más coherente con los cubos de varias capas. [8]
Girando todo el cubo:
Las letras x , y y z se utilizan para indicar rotaciones del cubo. x significa rotar el cubo en la dirección R. y significa la rotación del cubo en la dirección U. z significa la rotación del cubo en la dirección F. Estas rotaciones del cubo se utilizan a menudo en algoritmos para hacerlos más suaves y rápidos. Al igual que con los giros regulares, un 2 significa media vuelta y una prima (') indica un giro en sentido antihorario. Tenga en cuenta que estas rotaciones espaciales suelen representarse con letras minúsculas.
Se puede demostrar, contando argumentos, que existen posiciones que necesitan al menos 18 movimientos para resolverse. Para demostrarlo, primero se cuenta el número de posiciones de cubo que existen en total y luego se cuenta el número de posiciones que se pueden lograr utilizando como máximo 17 movimientos a partir de un cubo resuelto. Resulta que el último número es menor.
Este argumento no fue mejorado durante muchos años. Además, no es una prueba constructiva : no muestra una posición concreta que necesite tantos movimientos. Se conjeturó que el llamado superflip sería una posición que es muy difícil. Un cubo de Rubik está en el patrón de superflip cuando cada pieza de esquina está en la posición correcta, pero cada pieza de borde está orientada incorrectamente. [9] En 1992, Dik T. Winter encontró una solución para el superflip con 20 vueltas de cara, cuya minimalidad fue demostrada 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 el superflip en 24 cuartos de vuelta, con su minimalidad demostrada por Jerry Bryan. [9] En 1998, se encontró una nueva posición que requiere más de 24 cuartos de vuelta para resolverse. La posición, que se llamó un 'superflip compuesto con cuatro puntos' necesita 26 cuartos de vuelta. [10]
Los primeros límites superiores se basaron en algoritmos "humanos". Al combinar los peores escenarios posibles para cada parte de estos algoritmos, se determinó que el límite superior típico era de alrededor de 100.
Tal vez 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. [11] [12] 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. [11] [13] Poco después, los cubistas de Cambridge de Conway informaron que el cubo podía restaurarse en como máximo 94 movimientos. [11] [14]
El descubrimiento, conocido como "descenso a través de subgrupos anidados", fue realizado por Morwen Thistlethwaite ; los detalles del algoritmo de Thistlethwaite fueron publicados en Scientific American en 1981 por Douglas Hofstadter . Los enfoques del cubo que llevaron a algoritmos con muy pocos movimientos se basan en la teoría de grupos y en extensas búsquedas informáticas. La idea de Thistlethwaite era dividir el problema en subproblemas. Mientras que los algoritmos hasta ese momento dividían el problema observando las partes del cubo que debían permanecer fijas, él lo dividió restringiendo el tipo de movimientos que se podían ejecutar. En particular, dividió el grupo del cubo en la siguiente cadena de subgrupos:
A continuación preparó tablas para cada uno de los espacios de clase lateral derecha . Para cada elemento encontró una secuencia de movimientos que lo llevaba al siguiente grupo más pequeño. Después de estas preparaciones trabajó de la siguiente manera. Un cubo al azar está en el grupo general de cubos . A continuación encontró este elemento en el espacio de clase lateral derecha . Aplicó el proceso correspondiente al cubo. Esto lo llevó a un cubo en . A continuación buscó un proceso que lleva el cubo a , junto a y finalmente a .
Aunque todo el grupo de cubos es muy grande (~4,3×10 19 ), los espacios de coconjuntos derechos y son mucho más pequeños. El espacio de coconjuntos es el más grande y contiene solo 1082565 elementos. La cantidad de movimientos que requiere este algoritmo es la suma del proceso más grande en cada paso.
Inicialmente, Thistlethwaite demostró que cualquier configuración podía resolverse en un máximo de 85 movimientos. En enero de 1980 mejoró su estrategia para obtener un máximo de 80 movimientos. Más tarde, ese mismo año, redujo el número a 63, y luego de nuevo a 52. [11] Al buscar exhaustivamente en los espacios de clases laterales, se descubrió más tarde que el peor número posible de movimientos para cada etapa era 7, 10, 13 y 15, lo que da un total de 45 movimientos como máximo. [16] Ha habido implementaciones del algoritmo de Thistlewaite en varios lenguajes informáticos. [17]
El algoritmo de Thistlethwaite fue mejorado por Herbert Kociemba en 1992. Redujo el número de grupos intermedios a sólo dos:
Al igual que con el algoritmo de Thistlethwaite , buscaría a través del espacio de clases laterales derecho para llevar el cubo al grupo . A continuación, buscó la solución óptima para el grupo . Las búsquedas en y se realizaron con un método equivalente a la profundización iterativa A* (IDA*). La búsqueda en necesita como máximo 12 movimientos y la búsqueda en como máximo 18 movimientos, como demostró Michael Reid en 1995. Al generar también soluciones subóptimas que llevan el cubo al grupo y buscar soluciones cortas en , generalmente se obtienen soluciones generales mucho más cortas. Usando este algoritmo, las soluciones se encuentran típicamente de menos de 21 movimientos, aunque no hay prueba de que siempre lo hará.
En 1995, Michael Reid demostró que, utilizando estos dos grupos, cada posición puede resolverse en un máximo de 29 giros de frente o en 42 cuartos de giro. Este resultado fue mejorado por Silviu Radu en 2005 hasta 40.
A primera vista, este algoritmo parece ser prácticamente ineficiente: si contiene 18 movimientos posibles (cada movimiento, su primo y su rotación de 180 grados), eso deja (más de 1 cuatrillón) de estados del cubo para buscar. Incluso con un algoritmo informático basado en heurística como IDA* , que puede limitarlo 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 . [18] Cuando se dispone del número exacto de movimientos necesarios para alcanzar , la búsqueda se vuelve prácticamente instantánea: solo hay que generar 18 estados del cubo para cada uno de los 12 movimientos y elegir el que tenga la heurística más baja cada vez. Esto permite que la segunda heurística, la de , sea menos precisa y aún así permita calcular una solución en un tiempo razonable en una computadora moderna.
El uso de estas soluciones grupales combinadas con búsquedas en la computadora generalmente arrojará soluciones muy breves y rápidas. Pero estas soluciones no siempre vienen con una garantía de su minimalismo. Para buscar específicamente soluciones mínimas se necesitaba un nuevo enfoque.
En 1997, Richard Korf anunció un algoritmo con el que había resuelto de forma óptima instancias aleatorias del cubo. De los diez cubos aleatorios que creó, ninguno requirió más de 18 giros de cara. El método que utilizó se llama IDA* y se describe en su artículo "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases" (Encontrar soluciones óptimas para el cubo de Rubik utilizando bases de datos de patrones). [19] Korf describe este método de la siguiente manera:
Funciona más o menos de la siguiente manera. Primero identificó una serie de subproblemas que son lo suficientemente pequeños como para resolverlos de manera óptima. Utilizó:
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 el cubo entero.
Dado un cubo aleatorio C, se resuelve como profundización iterativa . Primero se generan todos los cubos que son el resultado de aplicarles 1 movimiento. Es decir, C * F, C * U, ... A continuación, de esta lista, se generan todos los cubos que son el resultado de aplicarles dos movimientos. Luego, tres movimientos y así sucesivamente. Si en algún momento se encuentra un cubo que necesita demasiados movimientos según los límites inferiores 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. En general, no se sabe cuántas iteraciones necesitará este algoritmo para alcanzar una solución óptima. Puede encontrarse una implementación de este algoritmo aquí. [20]
En 2006, Silviu Radu mejoró aún más sus métodos para demostrar que cada posición puede resolverse en un máximo de 27 giros de cara o 35 cuartos de vuelta. [21] En 2007, Daniel Kunkle y Gene Cooperman utilizaron una supercomputadora para demostrar que todos los cubos sin resolver pueden resolverse en no más de 26 movimientos (en la métrica de giro de cara). En lugar de intentar resolver cada uno de los miles de millones de variaciones de forma 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 en unos pocos movimientos adicionales. Se demostró que todos eran solucionables en 29 movimientos, y la mayoría en 26. Aquellos que inicialmente no podían resolverse en 26 movimientos se resolvieron explícitamente y se demostró que también podían resolverse en 26 movimientos. [22] [23]
En una prueba computacional de 2008, Tomas Rokicki informó que todos los cubos sin resolver podían resolverse en 25 movimientos o menos. [24] Esto se redujo posteriormente a 23 movimientos. [25] En agosto de 2008, Rokicki anunció que tenía una prueba para 22 movimientos. [26]
Finalmente, en 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge dieron la prueba final asistida por computadora de que todas las posiciones del cubo podían resolverse con un máximo de 20 giros de cara. [2] En 2009, Tomas Rokicki demostró que 29 movimientos en la métrica de un cuarto de vuelta son suficientes para resolver cualquier cubo desordenado. [27] 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 de cara y de cuarto de giro difieren en la naturaleza de sus antípodas. [3] Un antípoda es un cubo desordenado que está máximamente lejos de resolverse, uno que requiere el número máximo de movimientos para resolverse. En la métrica de medio giro con un número máximo de 20, hay cientos de millones de tales posiciones. En la métrica de cuarto de giro, solo se conoce una única 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 distancia de cuarto de giro de 26. Incluso a la distancia 25, solo se sabe que existen dos posiciones (y sus rotaciones). [3] [28] A la distancia 24, tal vez existan 150.000 posiciones.
