resolución del cubo de rubik

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
analizarondistintas 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 solucionespropuestas 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 elaná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 explicara 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í decualquier 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 sincambiar 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
Elobjetivo 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. 4
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,...