Rubik

34ª Jornadas Argentinas de Informática e Investigación Operativa

“Algoritmos de resolución para el cubo de Rubik”

Categoría: Trabajos de Cátedra Área: “Algoritmos, lenguajes y programación” Autores: Ridao Freitas, Iván Osvaldo (iridao@exa.unicen.edu.ar) Vidal, Santiago Agustín (svidal@exa.unicen.edu.ar) Directora del trabajo: Laura Felice

Universidad Nacional del Centro de la Provinciade Buenos Aires

34ª Jornadas Argentinas de Informática e Investigación Operativa

“Algoritmos de resolución para el cubo de Rubik”

Categoría: Trabajos de Cátedra Área: “Algoritmos, lenguajes y programación”

Índice Resumen ................................................................................................... 1. Introducción......................................................................................... 1.1 Objetivo del juego ............................................................................ 1.2 Definiciones básicas ....................................................................... 1.2.1 Las piezas del cubo ................................................................... 1.2.2 Notación y movimientos básicos.............................................. 2. Metodología .......................................................................................... 3. Implementación ................................................................................... 3.1 Diseño de clases .............................................................................. 3.2 Desarrollo de la solución............................................................... 3.3 Paso 1: Obtención de la Cruz ......................................................... 3.4 Análisis de complejidad temporal .................................................. 3.5 Algoritmo Principiante .................................................................. 3.5.1 Paso 2: Las Aristas Centrales ................................................... 3.5.2 Paso 3: La CaraSuperior .......................................................... 3.5.3 Paso 4: La Cruz en la cara Inferior ........................................... 3.5.4 Paso 5: Colocación de las aristas en la cara Inferior ................ 3.5.5 Paso 6: Colocación de las esquinas en la cara Inferior ............. 3.5.6 Paso 7: Orientación de las esquinas en la cara Inferior ............ 3.5.7 PromedioGeneral ..................................................................... 3.6 Algoritmo Experto .......................................................................... 3.6.1 Paso 2: Orientación de a capa Superior y Media ...................... 3.6.2 Paso 3: Orientación de la capa Inferior .................................... 3.6.3 Paso 4: Permutación de la capa Inferior................................... 3.6.4 Promedio General ..................................................................... 4. Otros Aspectos Importantes ............................................................... 5. Conclusiones ........................................................................................ 6. Referencias.......................................................................................... 3 3 3 4 4 4 4 5 5 5 7 7 8 8 8 9 9 10 10 11 11 11 11 12 12 12 13 13

2

RESUMEN El objetivo de este trabajo fue diseñar e implementar un algoritmo que resuelva el problema de armar el cubo de Rubik (o cubo mágico), dada cualquiera de las más de 43 trillones de posibles configuraciones de éste. Para esto se realizó un trabajo de investigación mediante el cual se procedió a delinearlos pasos para un algoritmo basado en la técnica de Backtracking. Se analizaron distintas heurísticas para reducir el espacio de búsqueda y así obtener un algoritmo más eficiente. No estando totalmente satisfechos con esta primera solución, se implementó un segundo programa del mismo tipo, aunque mucho más complejo y sofisticado que logró reducir a la mitad la cantidad de movimientos en los cuales...