cubo de rubick

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 laProvincia de 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 Cara Superior ..........................................................
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 Promedio General .....................................................................
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 lacapa 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 serealizó un trabajo de investigación mediante el
cual se procedió a delinear los 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...