PDF de programación - Algoritmos de resolución para el cubo de 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 ([email protected])
Vidal, Santiago Agustín ([email protected])
Directora del trabajo: Laura Felice



Universidad Nacional del Centro
de la Provincia 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 ................................................................................................... 3
1. Introducción ......................................................................................... 3
1.1 Objetivo del juego ............................................................................ 3
1.2 Definiciones básicas ....................................................................... 4
1.2.1 Las piezas del cubo ................................................................... 4
1.2.2 Notación y movimientos básicos .............................................. 4
2. Metodología .......................................................................................... 4
3. Implementación ................................................................................... 5
3.1 Diseño de clases .............................................................................. 5
3.2 Desarrollo de la solución ............................................................... 5
3.3 Paso 1: Obtención de la Cruz ......................................................... 7
3.4 Análisis de complejidad temporal .................................................. 7
3.5 Algoritmo Principiante .................................................................. 8
3.5.1 Paso 2: Las Aristas Centrales ................................................... 8
3.5.2 Paso 3: La Cara Superior .......................................................... 8
3.5.3 Paso 4: La Cruz en la cara Inferior ........................................... 9
3.5.4 Paso 5: Colocación de las aristas en la cara Inferior ................ 9
3.5.5 Paso 6: Colocación de las esquinas en la cara Inferior ............. 10
3.5.6 Paso 7: Orientación de las esquinas en la cara Inferior ............ 10
3.5.7 Promedio General ..................................................................... 11
3.6 Algoritmo Experto .......................................................................... 11
3.6.1 Paso 2: Orientación de a capa Superior y Media ...................... 11
3.6.2 Paso 3: Orientación de la capa Inferior .................................... 11
3.6.3 Paso 4: Permutación de la capa Inferior ................................... 12
3.6.4 Promedio General ..................................................................... 12
4. Otros Aspectos Importantes ............................................................... 12
5. Conclusiones ........................................................................................ 13
6. Referencias .......................................................................................... 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 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 sofisticado que logró reducir a la
mitad la cantidad de movimientos en los cuales se arma el cubo. Se describe en este trabajo las
dos soluciones propuestas y una comparación entre ambas.
Para darle una funcionalidad real al programa se le provee al usuario la posibilidad de cargar
cualquier cubo mediante una interfaz gráfica amigable. Cabe destacar que esta carga va
acompañada de un conjunto complejo de comprobaciones que cerciora configuraciones válidas.
Este trabajo fue realizado como proyecto final para una materia que introduce en el análisis y
el diseño de algoritmos. La misma es dictada en segundo año de una carrera de Informática.
El lenguaje utilizado para la implementación fue C++ y el entorno de desarrollo Borland
Builder C++.

1.INTRODUCCIÓN


El famoso cubo de Rubik fue inventado en el año 1974 por un profesor de Arquitectura de la
Universidad de Budapest, en Hungría, llamado Erno Rubik [10]. El propósito fue explicar a sus
alumnos algunos conceptos relacionados con el volumen y el espacio, pero luego de algún
tiempo el juego se hizo tan famoso que fue lanzado al mercado internacional.
El cubo de Rubik es un bloque cúbico con su superficie subdividida de modo que cada cara
consiste en nueve cuadrados. Cada cara se puede rotar, dando el aspecto de una rebanada entera
del bloque que rota sobre sí mismo. Esto da la impresión de que el cubo está compuesto de 27
cubos más pequeños (3 × 3 × 3). En su estado original cada cara del cubo es de un color, pero la
rotación de cada una de estas permite que los cubos más pequeños sean combinados de muchas
maneras. Tal es así que el cubo puede tener más de 43 trillones de diversas posiciones. Esto
deriva de que, por una parte podemos combinar entre sí de cualquier forma todas las esquinas,
lo que da lugar a 8! posibilidades. Con las aristas pasa lo mismo, es decir, que podemos
combinarlas de todas las formas posibles lo que da lugar a 12! posibilidades, pero la
permutación total de esquinas y aristas debe ser par lo que nos elimina la mitad de las
posibilidades. Por otra parte, podemos rotar todas las esquinas como queramos salvo una sin
cambiar nada más en el cubo. La orientación de la última esquina vendrá determinada por la que
tengan las otras siete y esto nos crea 37 posibilidades. Con las aristas pasa lo mismo, es decir,
nos aparecen 211 posibilidades más. En total tendremos que el número de permutaciones
posibles en el Cubo de Rubik es de:

(8! 12! 37 211)/2 = 43.252.003.274.489.856.000 [5]

1.1 Objetivo del juego
El objetivo básico del juego es restaurar el cubo a su condición original. Se deben utilizar las
diferentes rotaciones que el cubo permite, en cada uno de sus lados, para ir llevando cada pieza
de éste a su correcta ubicación, logrando así que cada cara sea de un único color.



3

1.2 Definiciones básicas

1.2.1 Las piezas del cubo

El cubo está formado por 3 clases distintas de piezas: las
centrales, las aristas y las esquinas. Cada una de estas piezas
se caracteriza porque poseen 1, 2 ó 3 colores
respectivamente. Es importante notar que en realidad son
las aristas y las esquinas las que se mueven, pues las piezas
centrales siempre guardan la misma posición relativa entre
ellas. Todos los movimientos que pueden hacerse con el
cubo se reducen a girar una o más veces las caras del cubo,
sin desplazar de su posición las piezas centrales.



1.2.2 Notación y movimientos básicos
Lo primero por realizar a la hora de expresar soluciones para el cubo es efectuar una notación
adecuada; por lo que se nombra cada cara con una letra mayúscula para describir los
movimientos sobre el cubo:
La cara de Arriba: A
La cara de aBajo: B
La cara de la Izquierda: I
La cara de la Derecha: D
La cara del Frente: F
La cara de aTrás: T


Cuando se nombre una cara por su letra, va a significar (en términos de movimiento) un giro
de un cuarto de vuelta (90 grados) en la dirección de las agujas del reloj. Es decir si decimos el
movimiento A, esto quiere decir un giro de un cuarto de vuelta de la cara de Arriba, en el
sentido de las agujas del reloj. Del mismo modo, el movimiento contrario (es decir, un giro de
un cuarto de vuelta en el sentido contrario a las agujas del reloj) estará indicado por A'. En tanto
que, un giro de media vuelta (180 grados) se indica como A2. Es importante aclarar que hacer
A, A’ o A2 equivale, en nuestra notación, a realizar un único movimiento.
Una secuencia de movimientos es una serie de letras mayúsculas que representan giros que
deben aplicarse sucesivamente sobre el cubo. Así, la secuencia DAD' significa un giro de la cara
Derecha de 90 grados en el sentido de las agujas del reloj, seguido de un giro de la cara de
Arriba de 90 grados en el mismo sentido, seguido de un giro de 90 grados de la cara Derecha en
sentido contrario a las agujas del reloj.

Este artículo está organizado de la siguiente manera. La sección 2 introduce brevemente la
metodología utilizada para el desarrollo del programa. La sección 3 explica detalles de la
implementación con las clases utilizadas y se describen los algoritmos implementados para la
resolución del cubo. En la sección siguiente se detallan otros aspectos importantes en cuanto