Usé Python y una búsqueda de amplitud de 2 caras para resolver un cubo de Rubiks de 2x2.
Inspirado en el proyecto del MIT 6.006. Creado desde cero de forma única.
https://youtu.be/ZHxLO6fubaU
Creé la API, el algoritmo y la GUI del cubo desde cero. Cada uno de los 6 lados tiene 4 cuadrados diferentes, lo que da como resultado 24 cuadrados. Además, hay un total de 8 esquinas que forman el cubo, cada una de las cuales tiene 3 orientaciones y, por tanto, va junto con los 24 cuadrados.
Definí cada una de las 24 subsecciones de cada lado como una cadena con 'xyz' como formato donde x es el color que se enfrenta inmediatamente y y y z van en el sentido de las agujas del reloj alrededor del cubo para esa esquina.
Di la vuelta al cubo y asigné a cada lado un número fijo que representaba el estado resuelto. Por ejemplo, 0, 1, 2, 3 son las 4 partes del lado blanco que mira hacia el frente, donde 0 está en la parte superior izquierda y las otras van en el sentido de las agujas del reloj.
Hay 12 movimientos que se pueden realizar en el cubo. Derecha, izquierda, arriba, abajo, adelante, atrás. Cada uno de estos también tiene sus movimientos en sentido contrario a las agujas del reloj, por lo que 6x2 = 12 movimientos. Cada uno de estos 12 manipula la mitad del cubo para obtener 12 cuadrados. Para realizar estos movimientos, creé diccionarios para cada uno de los 6 en el sentido de las agujas del reloj para los cuales el subcuadrado gira desde la posición original a la siguiente. Para hacer los números primos, simplemente cambié las claves y los valores.
Resolver este problema es especialmente complicado debido a la enorme cantidad de permutaciones posibles del cubo. Hay 24 subcuadrados y eso resulta en 24P24 = 24!. Esto tiene la magnitud de 10^23. Hay menos de esta cantidad debido a determinadas situaciones, pero el número sigue siendo enorme.
Para crear el árbol, tendría que ejecutar cada uno de los movimientos y ejecutar todos los movimientos desde los movimientos, lo que se vuelve muy grande. 12^altura del árbol. Pude limitar este tamaño creando un dictado de las posiciones visitadas para que no rehaga la acción para permutaciones visitadas anteriormente.
Comencé creando un BFS de 1 cara, pero eso alcanzaría el límite de recursividad ya que el árbol de ramificación se volvería demasiado grande. Para solucionar este problema, utilicé un BFS de 2 caras alternando la creación de ramas desde la solución inicial y final. Crearía los árboles y comprobaría si el lado opuesto ya había encontrado el punto. Si lo hiciera, devolvería el punto de conexión.
Durante todo esto, cada nodo guarda su padre (para la ramificación frontal) o su hijo (para la ramificación trasera). Para encontrar la ruta que tomó, encontré recursivamente al padre del nodo de conexión y luego a todos los hijos de ese punto. Esto resultó en una variedad de posiciones que tomó desde la revuelta hasta la resuelta.
Este proyecto aplicó mi uso de la teoría de grafos y Breadth First Search . Mejoré mi habilidad en Python y recursividad. También descubrí experimentalmente que los movimientos máximos para resolver un cubo de 2x2 son 11 movimientos, ya que nunca pude encontrar una solución que tomara más tiempo.
Aprendí a usar la biblioteca tkinter para crear una GUI para el proyecto.
