Programando el Cubo de Rubik (I)

Desde un tiempo, me rondaba por la cabeza hacer un programa que resolviera el cubo de Rubik. Hace años, estuve haciendo algunos bocetos, y tirando algunas líneas de código, pero lo dejé a medias, sin completarlo. Voy a retomarlo tratando de trabajar por partes, es decir, documentando mis avances en éste Blog, entrada trás entrada. 

Las fases de trabajo son, desde definir los requisitos del programa, hacer un diseño razonable y  que sea suficientemente flexible. Además, hay que definir cómo implementarlo en  código fuente. Una vez escrito el código, se debería diseñar una batería de pruebas, para verificar la corrección y eficiencia del programa, viendo cómo aplica una estrategias de resolución al cubo físico. Sin más, he pensado en la bien conocidas solución por 3 capas, que se puede encontrar en muchos sitios y foros en internet (http://www.rubikaz.com/).

En principio, no quiero hacer un diseño demasiado genérico, yendo directamente a la resolución concreta del problema del cubo de Rubik. Tampoco quiero hacer una programación imperativa clásica, que sea difícil de seguir, poco clara y farragosa de entender. Esto es para los fanáticos del ensamblador :).

Para que llegue a la gran audiencia, voy utilizar el lenguaje C++, orientado a objetos, correindo bajo Linux/Gnu Debian. La orientación a objetos permite repartir las responsabilidades y encapsulando las diferentes funcionalidades, así como desacoplar lo máximo posible (buen diseño) las tareas a realizar por el programa.

Respecto a los gráficos, no he pensado en nada complejo.  Simplemente voy a trabajar en modo texto, siendo necesario un cubo físico, para comprobar las soluciones en modo texto entregadas por el programa.   

Es muy importante pensar bien cómo representar el cubo, con sus caras, caritas, colores y operaciones de girado. Para ello, voy a utilizar una notación bien conocida por los "profesionales" del cubo de Rubik.  

¿Cómo es esta notación?. Pues bien, desde que el cubo tiene 6 caras, basta asociar a cada cara una letra, o bien una letra con una prima(') . Esto indicará un giro en sentido horario o anti-horario de la cara, según tenga o no prima. Las caras se denotan:

F: Front, B: Back, L: Left, R: Right, U:Up, D: Down, 

es decir, en castellano, delantera, trasera, izquierda, derecha, arriba y abajo, respectivamente.  

Además, si colocamos un dos delante de una letra, esto indica un giro de 180 grados.

De esta forma, podemos presentar cualquier combinación de movimientos. Veamos un ejemplo a continuación. Suponer que tenemos la siguiente cadena de letras definidas como antes: 

FB2DF'B', 

Esta ristra de caracteres anterior querría decir lo siguiente: 

1. Giramos la cara delantera 90 grados sentido horario: F
2. Giramos cara trasera 90 grados sentido horario: B
3. Giramos cara de abajo 180 grados: 2D
4. Giramos cara delantera 90' sentido anti-horario: F'
5. y por último giramos 90 grados la cara trasera en sentido anti-horario: B'

Ahora, pasamos a la parte de la programación, que da título a esta entrada. Un programa en C++, debería ser pensado, con el objetivo de repartir las funcionalidades o responsabilidades requeridas, entre las diferentes clases que lo componen. Por tanto, definamos que es lo que queremos de nuestro programa claramente:

1. Representar cualquier estado del cubo de Rubik: Situación de cada cara y color.
2. Mezclador del cubo de Rubik, mediante un número de giros indicado por el usuario.
3. Buscador de la posición de una carilla cualquiera, ya sea una arista, o un vértice del cubo.
4. Desarrollar un algoritmo que resuelva  del cubo de Rubik desde cualquier estado.
5. Aceptar por consola o fichero, la descripción del estado de un cubo de Rubik, a ser resuelto.
6. Presentar la salida de la estrategia, en notación de Rubik (vista arriba), la solución al cubo desde un estado aleatorio sacado del mezclador, o introducido por el usuario. 
7. El usuario debe ser capaz de resolver su cubo de Rubik físico, a partir de la solución.

Podríamos pedir más funcionalidades, como puede ser trabajar con diferentes estrategias de resolución y devolver estadísticas para cada una de las estrategias. Incluso, hacer un programa más genérico, que permita trabajar con cubos de lado mayor a tres. No voy a entrar en esas complejidades, hasta que al menos hayamos acabado con una primera versión sencilla, que sea capaz de resolverlo con una estrategia básica.

¿Cómo realizamos el diseño del programa?. Pues bueno, después de jugar con el cubo físico y, garabatear algunos dibujos y diagramas para representar las operaciones y el estado del cubo, he llegado a un diseño de clases para C++ mas o menos bueno. Esto es un proceso algo intuitivo y creativo, así que es difícil de describir ordenadamente. Podría poner aquí esos diagramas, pero no serviría de mucho, ya que son bastante desordenado y subjetivos.
Ahora, veamos cómo el diseño, nos va a permitir distribuir las funcionalidades descritas. Estas podrían estar agrupadas utilizando las siguientes clases de objetos:

• Clase Cara: Encargada de representar y mantener los colores de las 9 carillas de una cara del cubo de Rubik, además de su disposición.  Es clave en esta clase, es su auto-referencia, para realizar conexiones entre instancias. Esto permitirá pasar información entre las caras conectadas, cuando se realice una operación de girado en alguna de ellas.
• Clase Rubik: Aglutinará 6 instancias de la clase Cara, además de encapsular las conexiones entre las instancias de las Caras,  y de las operaciones realizadas. 
• Clase Mezclador: Recibirá una instancia de clase Rubik, operando sobre ella, mezclando los colores mediante operaciones de giro en cada cara del la instancia de Rubik.
• Clase Estrategia: Encargada de recibir una instancia de Rubik, y aplicar una estrategia de resolución sobre la misma. Deberá entregar la lista de operaciones en notación de Rubik.

Acabamos aquí con esta entrega. En la próxima, continuaremos definiendo las interfaces de las clases del diseño anterior. Espero que os haya gustando. Cualquier sugerencia o pregunta es bienvenida.
Saludos ;)