Soluciones óptimas para el cubo de Rubik

El algoritmo de cuatro fases de Thistlethwaite no está diseñado para buscar una solución óptima, ya que su promedio de movimientos es de aproximadamente 31. ^{[ 12 ]} Sin embargo, es un método de resolución interesante desde un punto de vista teórico.

El avance en la determinación de una cota superior, conocido como "descenso a través de subgrupos anidados", fue descubierto por Morwen Thistlethwaite ; los detalles del algoritmo de Thistlethwaite fueron publicados en Scientific American en 1981 por Douglas Hofstadter . Los enfoques del cubo que condujeron a algoritmos con muy pocos movimientos se basan en la teoría de grupos y en extensas búsquedas computacionales. La idea de Thistlethwaite fue dividir el problema en subproblemas. Mientras que los algoritmos hasta ese momento dividían el problema considerando las partes del cubo que debían permanecer fijas, él lo dividió restringiendo el tipo de movimientos que podían ejecutarse. En particular, dividió el grupo del cubo 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,U2,D2\rangle }$
• ${\displaystyle G_{2}=\langle L,R,F2,B2,U2,D2\rangle }$
• ${\displaystyle G_{3}=\langle L2,R2,F2,B2,U2,D2\rangle }$
• ${\displaystyle G_{4}=\{1\}}$

(En el ejemplo resuelto anterior,${\displaystyle G_{1}}$se reemplaza por su equivalente <L,R,F2,B2,U,D> y${\displaystyle G_{2}}$se reemplaza por su equivalente <L2,R2,F2,B2,U,D> - si desea ver los subgrupos como se describió anteriormente, gire todo el cubo de manera que la pieza central azul o verde quede hacia arriba y la pieza central naranja o roja quede hacia el frente.

A continuación preparó tablas para cada uno de los espacios cociente derechos.${\displaystyle G_{i}\setminus G_{i+1}}$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 general de cubos.${\displaystyle G_{0}}$A continuación, encontró este elemento en el espacio de clases laterales derecho.${\displaystyle G_{0}\setminus G_{1}}$. Aplicó el proceso correspondiente al cubo. Esto lo convirtió en un cubo en${\displaystyle G_{1}}$. Luego buscó un proceso que lleva el cubo a${\displaystyle G_{2}}$, junto a${\displaystyle G_{3}}$y finalmente a${\displaystyle G_{4}}$.

Aunque todo el grupo de cubos${\displaystyle G_{0}}$es muy grande (tiene ~ 43 × 10 ¹⁸ elementos), los espacios de clases laterales derechas${\displaystyle G_{0}\setminus G_{1},G_{1}\setminus G_{2},G_{2}\setminus G_{3}}$y${\displaystyle G_{3}\setminus G_{4}}$son mucho más pequeños: ^{[ 13 ]}

• Fase 1 (espacio cociente${\displaystyle G_{0}\setminus G_{1}}$) contiene 2.048 configuraciones
• Fase 2 (espacio coetáneo)${\displaystyle G_{1}\setminus G_{2}}$) contiene 1.082.565 configuraciones
• Fase 3 (espacio coset)${\displaystyle G_{2}\setminus G_{3}}$) contiene 29.400 configuraciones
• Fase 4 (espacio coset)${\displaystyle G_{3}\setminus G_{4}}$) contiene 663.552 configuraciones

Inicialmente, Thistlethwaite demostró que cualquier configuración podía resolverse en un máximo de 85 movimientos utilizando un método totalmente diferente. 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 utilizando un nuevo enfoque, y luego nuevamente a 52 utilizando un enfoque completamente diferente que ahora se conoce como el algoritmo de Thistlethwaite. ^{[ 14 ]} Al buscar exhaustivamente en los espacios de clases laterales, se descubrió posteriormente que el peor recuento posible de movimientos para cada fase es 7, 10, 13 y 15, lo que da un total de un máximo de 45 movimientos. Existen implementaciones del algoritmo de Thistlewaite en varios lenguajes de programación.

La idea principal detrás del algoritmo de la lista de 4 (a veces denominado algoritmo de Shamir) es una búsqueda bidireccional, también conocida como enfoque de encuentro en el medio . Un grupo de investigadores —Adi Shamir , Amos Fiat , Shahar Mozes , Ilan Shimshoni y Gábor Tardos— demostraron cómo aplicar el algoritmo al cubo de Rubik en 1989, ^{[ 15 ]} basándose en un trabajo anterior de Richard Schroeppel y Adi Shamir de enero de 1980 (que se publicó en 1981). ^{[ 16 ]}

El algoritmo de la lista de 4 no está diseñado para buscar la solución óptima lo más rápido posible. Su propósito es encontrar una solución de como máximo 20 movimientos, pero sin ninguna garantía de que la solución encontrada sea la óptima. Si el algoritmo no se detiene al encontrar la primera solución, puede encontrar todas las soluciones, incluidas las óptimas. Sin embargo, el primer informe de soluciones óptimas para cubos desordenados aleatoriamente provino de Richard E. Korf en 1997, utilizando su propio algoritmo. El tiempo de búsqueda requerido para que el algoritmo de la lista de 4 encuentre una solución óptima es considerablemente mayor en comparación con los algoritmos de Kociemba o Feather.

La búsqueda bidireccional funciona explorando simultáneamente desde el estado desordenado hacia adelante y desde el estado resuelto hacia atrás, hasta alcanzar un estado común en ambas direcciones. La solución se obtiene combinando la ruta de búsqueda hacia adelante con la inversa de la ruta de búsqueda hacia atrás.

Para encontrar una solución utilizando el algoritmo de la lista de 4 elementos, primero se almacena en la RAM una lista con las 621.649 permutaciones que alcanzan profundidades de 0 a 5. Mediante la multiplicación inteligente de todos los pares posibles de elementos de esa lista y la ordenación de los productos resultantes, se generan todas las permutaciones que alcanzan profundidades de 0 a 10 en orden lexicográfico a partir de estados tanto aleatorios como resueltos, lo que finalmente lleva a encontrar una coincidencia en su intersección. ^{[ 17 ]} Como consecuencia del ordenamiento lexicográfico, es posible eliminar permutaciones duplicadas y contar el número de permutaciones únicas sin almacenar ninguno de los productos creados en la RAM.

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,R,L,F,B\rangle }$
• ${\displaystyle G_{1}=\langle U,D,R2,L2,F2,B2\rangle }$lo cual es equivalente a Thistlethwaite${\displaystyle G_{2}}$
• ${\displaystyle G_{2}=\{1\}}$

El algoritmo de dos fases de Kociemba no está diseñado para buscar una solución óptima; su propósito es encontrar rápidamente una solución subóptima razonablemente corta. Un cubo desordenado aleatoriamente se resolvería normalmente en una fracción de segundo en 20 movimientos o menos, pero sin ninguna garantía de que la solución encontrada sea óptima. Si bien es técnicamente posible buscar una solución óptima utilizando el algoritmo de Kociemba reduciendo un solucionador de dos fases a uno de una sola fase (solo se usaría la fase 1 hasta que el cubo esté completamente resuelto, sin realizar ninguna operación de la fase 2), en ese caso sería necesario un mayor uso del hardware, ya que un solucionador óptimo rápido requiere muchos más recursos de computación que un solucionador subóptimo igualmente rápido.

Al igual que con el algoritmo de Thistlethwaite , buscaría en el espacio de clases laterales correcto.${\displaystyle G_{0}\setminus G_{1}}$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_{0}\setminus G_{1}}$y${\displaystyle G_{1}}$Ambos se realizaron con un método equivalente al método de profundización iterativa A* (IDA*). La búsqueda en${\displaystyle G_{0}\setminus G_{1}}$necesita como máximo 12 movimientos y la búsqueda en${\displaystyle G_{1}}$como máximo 18 movimientos, como demostró Michael Reid en 1995. Al generar también soluciones subóptimas que llevan el cubo al grupo${\displaystyle G_{1}}$y buscando soluciones cortas en${\displaystyle G_{1}}$Por lo general, se obtienen soluciones globales mucho más cortas.

En 1995, Michael Reid demostró que, utilizando estos dos grupos, cualquier posición puede resolverse en un máximo de 29 giros de cara, o en 42 cuartos de giro. Este resultado fue mejorado por Silviu Radu en 2005, reduciéndolo a 40 cuartos de giro.

A primera vista, este algoritmo parece ser prácticamente ineficiente: si${\displaystyle G_{0}}$contiene 18 movimientos posibles (cada movimiento, su primo y su rotación de 180 grados), que deja${\displaystyle 18^{12}}$(más de 1 cuatrillón) de estados cúbicos para buscar. Incluso con un algoritmo informático basado en heurísticas como IDA* , que puede reducirlo considerablemente, buscar a través de tantos estados probablemente no sea práctico. Para resolver este problema, Kociemba ideó una tabla de búsqueda que proporciona una heurística exacta para${\displaystyle G_{0}}$. ^{[ 18 ]} Cuando el número exacto de movimientos necesarios para alcanzar${\displaystyle G_{1}}$está disponible, la búsqueda de soluciones subóptimas se vuelve prácticamente instantánea (tenga en cuenta que la búsqueda de soluciones óptimas lleva mucho más tiempo): solo es necesario 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 la segunda heurística, la que para${\displaystyle G_{1}}$Para ser menos precisos, pero permitiendo que se pueda calcular una solución en un tiempo razonable en un ordenador moderno.

En 1997, Richard E. Korf escribió el primer programa para resolver cubos aleatorios de forma óptima. De los diez cubos aleatorios que resolvió, 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". ^{[ 19 ]} 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 el límite inferior de su longitud excede el límite de iteraciones actual.

Funciona aproximadamente de la siguiente manera. Primero identificó una serie de subproblemas lo suficientemente pequeños como para poder resolverse de forma óptima. Utilizó:

1. El cubo se limita solo a las esquinas, sin observar los bordes.
2. El cubo se limita a solo 6 aristas, sin tener en cuenta ni las esquinas ni las demás aristas.
3. El cubo se limita a las otras 6 aristas.

Es evidente que el número de movimientos necesarios para resolver cualquiera de estos subproblemas constituye un límite inferior para el número de movimientos necesarios para resolver el cubo completo.

Dado un cubo aleatorio C, se resuelve mediante un proceso iterativo de profundización . Primero, se generan todos los cubos que resultan de aplicarles un movimiento. Es decir, C * F, C * U, ... A continuación, de esta lista, se generan todos los cubos que resultan de aplicarles dos movimientos, luego tres movimientos, y así sucesivamente. Si en algún momento se encuentra un cubo que requiere demasiados movimientos, según los límites inferiores, para seguir siendo óptimo, se puede eliminar de la lista.

Si bien este algoritmo siempre encontrará una solución óptima, su tiempo de búsqueda es considerablemente mayor que el de los algoritmos de Kociemba o Feather.

En 2015, Michael Feather presentó en su sitio web un algoritmo único de dos fases. Este algoritmo es capaz de generar soluciones tanto subóptimas como óptimas en un tiempo razonable en un dispositivo moderno. ^{[ 20 ]} A diferencia de los algoritmos de Thistlethwaite o Kociemba, el algoritmo de Feather no se basa en gran medida en la teoría de grupos.

El cubo de Rubik se puede simplificar utilizando solo 3 colores en lugar de los 6 habituales. Generalmente, las caras opuestas comparten el mismo color. En un cubo de 6 colores, un cubo de 3 colores resuelto se representa mediante un estado en el que solo aparecen colores opuestos en las caras opuestas.

En resumen, el algoritmo de Feather funciona así: cualquier solución de 3 colores (en la fase 1) que surja de los nodos generados se busca (en la fase 2) en el array que contiene un total de 3.981.312 configuraciones y que incluye las distancias desde las soluciones intermedias de 3 colores hasta la solución final de 6 colores. Si la fase 2 tiene como máximo 8 movimientos* (de los cuales hay 117.265 configuraciones), se genera una solución. ^{[ 21 ]} Se puede considerar como una búsqueda por fuerza bruta mejorada mediante el uso de arrays de distancias para podar el árbol de búsqueda cuando sea posible, y también reduciendo el tamaño de los arrays de distancias de manera efectiva mediante la simetría cúbica. ^{[ 22 ]} *No existe ningún requisito real de que la fase 2 se limite a 8 movimientos, ya que el algoritmo es perfectamente capaz de trabajar con cualquier longitud para la fase 2, hasta un máximo de 16 movimientos. ^{[ 23 ] [ 24 ]}

Al buscar una solución óptima, el algoritmo de Feather encuentra soluciones subóptimas en el proceso. Esto representa una ventaja, ya que en muchos casos no necesita explorar hasta la profundidad de la solución óptima, puesto que ya ha encontrado una solución subóptima a una profundidad menor, igual a la longitud de la solución óptima. Por lo tanto, solo necesita completar la búsqueda hasta la profundidad n − 1 para demostrar que la solución de longitud n es óptima.

El algoritmo de Feather se implementó en el primer solucionador óptimo en línea del Cubo de Rubik, más específicamente en el primer solucionador de procesamiento del lado del cliente ( JavaScript ) con una interfaz gráfica de usuario que se ejecuta en un navegador web y que puede generar soluciones óptimas de manera oportuna. Esto incluye el cálculo de soluciones óptimas de 19 movimientos, ya que se presentan en aproximadamente el 3,4 % de todos los casos en un lote de cubos mezclados aleatoriamente. El solucionador tiene múltiples opciones para matrices de distancia de diferentes tamaños para maximizar el uso de la RAM disponible , y también utiliza todos los procesadores disponibles para obtener el mejor rendimiento de una amplia variedad de plataformas. ^{[ 25 ]}

Los algoritmos de 4 listas, Kociemba, Korf y Feather pueden ajustarse para encontrar siempre la solución óptima en HTM; el algoritmo de Thistlethwaite no puede hacerlo. Sin embargo, si se compara con un algoritmo de Feather de dos fases (tanto óptima como subóptima), entonces un algoritmo de Kociemba de una fase (óptima) y uno de dos fases (subóptima) deben considerarse algoritmos distintos.

Se sabe que los algoritmos de 4 listas, Kociemba y Korf siempre buscan a una profundidad n para demostrar que la solución encontrada es óptima, mientras que el algoritmo de Feather suele buscar a una profundidad n − 1 para demostrar que la solución encontrada es óptima, donde n es la longitud de la solución.

Los algoritmos de Korf, Kociemba y Feather utilizan la búsqueda IDA* , pero difieren en los componentes del cubo que se usan para las tablas de distancias (también conocidas como matrices de distancias, bases de datos de patrones, tablas de búsqueda o tablas de poda) para podar el árbol. El factor de ramificación para los tres algoritmos mencionados es de aproximadamente 13,35, lo que significa que tardarán aproximadamente 13,35 veces más en completar la búsqueda a profundidad n que la búsqueda a profundidad n − 1 .

El cubo de Rubik tiene un total de 48 simetrías. ^{[ 26 ]} Los solucionadores óptimos para los algoritmos de Korf y de 4 listas no explotan ninguna simetría del cubo. El solucionador óptimo para el algoritmo de Kociemba puede explotar 16 simetrías*. El solucionador óptimo para el algoritmo de Feather puede explotar las 48 simetrías. *16 simetrías por eje. Para explotar las 48 simetrías, el solucionador debe realizar una búsqueda triple, lo que significa que en lugar de buscar en un solo eje, tiene que buscar en los 3 ejes del cubo (eje arriba-abajo, eje adelante-atrás, eje derecha-izquierda) simultáneamente. ^{[ 27 ]}

Los algoritmos de Thistlethwaite, Kociemba de dos fases (subóptimo) y Feather de dos fases (óptimo y subóptimo) son todos algoritmos basados ​​en reducción:

• Algoritmo de Thistlethwaite: Cubo desordenado → Orientación de aristas (EO) → Reducción en dominó (DR) → Reducción de media vuelta (HTR) → Cubo resuelto
• Algoritmo de Kociemba: Cubo desordenado → DR → Cubo resuelto
• Algoritmo de Feather: Cubo desordenado → Reducción de cubo de 3 colores → Cubo resuelto

Mientras que los algoritmos de Thistlethwaite y Kociemba de dos fases se restringen más en cuanto a movimientos en cada fase siguiente, el algoritmo de Feather no se restringe en cuanto a movimientos en la fase 2. Además, existe una diferencia sustancial entre HTR y la reducción de cubo de 3 colores (HTR es un subconjunto de la reducción de cubo de 3 colores) aunque puedan parecer iguales a primera vista. ^{[ 28 ]} De manera similar al HTR de Thistlethwaite, la fase 2 del algoritmo de Feather también se puede resolver usando solo medias vueltas*, pero en ese caso no todas las configuraciones serían resolubles en un máximo de 8 medias vueltas. *Suponiendo que las secuencias en la fase 2 están limitadas a 8 movimientos.

Al comparar el factor de reducción entre ambos algoritmos de dos fases, la fase 1 del algoritmo de Feather reduce el cubo 19.508.428.800/3.981.312 = 4.900 veces más que la fase 1 del algoritmo de Kociemba.