El cubo de Rubik

Es un juguete con el que la mayoría de los niños han jugado en algún momento, pero el hallazgo del profesor de Ciencias de la Computación de la Universidad del Noreste Gene Cooperman y el estudiante graduado Dan Kunkle no es un juego de niños. Los dos han probado que 26 movimientos son suficientes para resolver cualquier configuración del cubo de Rubik – un nuevo récord. Históricamente la mejor marca estaba en 27 movimientos.

¿Por qué esta fascinación con este popular rompecabezas?

“El cubo de Rubik es una base de pruebas para problemas de búsqueda y enumeración”, dice Cooperman. “La búsqueda y enumeración es un gran campo de investigación que abarca a gran cantidad de investigadores trabajando en distintas disciplinas – desde la inteligencia artificial a las operaciones. El cubo de Rubik permite a los investigadores de distintas disciplinas comprar sus métodos en un único y conocido problema”.

Cooperman y Kunkle fueron capaces de conseguir su récord gracias a dos técnicas principales: Usaron 7 terabytes de discos distribuidos como extensión de la memoria RAM, para mantener en memoria grandes tablas y desarrollaron un nuevo y mucho más rápida forma de calcular movimientos, e incluso movimientos de grupos completos usando la Teoría de Grupos de las matemáticas.

Cooperman y Kunkle pusieron todas las configuraciones del cubo de Rubik en una familia de conjuntos de configuraciones (llamados familia de cosets en la Teoría de Grupos matemática). Entonces observaron los resultados de aplicar un sólo movimientos a todas las configuraciones de un coset a la vez. Simularon esto en un ordenador a razón de 100 000 000 de veces por segundo, usando una nueva técnica matemática de la Teoría de Grupos.

En mayo de 1997, el profesor de Ciencias de la Computación de UCLA Richard Korf anunció que había encontrado las primeras soluciones óptimas para el cubo de Rubik. Su investigación demostró que la solución óptima media es de 18 movimientos, y creía que cualquier cubo podría resolverse en no más de 20 movimientos. Sin embargo fue incapaz de demostrarlo, y nadie ha sido capaz de demostrar que se pudiese resolver en menos de 27 movimientos.

“Korf había escrito un programa que pasaba mucho tiempo hasta llegar a la solución óptima para estados simples del cubo de Rubik”, dice Kunkle. “Nuestro programa primero hace un precómputo y entonces, de forma muy rápida – en aproximadamente un segundo – halla una solución en 26 movimientos o menos para cualquier situación del cubo de Rubik.

Cooperman y Kunkle usaron ordenadores de Teragrid (teragrid.org) y del Noreste, parte del primer nodo de una beca de 200 000 dólares que Cooperman y sus colegas recibieron de la Fundación Nacional de Ciencia en 2006 para obtener 20 terabytes de almacenamiento.

El cubo de Rubik, que se inventó a finales de los años 70 por Erno Rubik de Hungría, es tal vez el rompecabezas combinatorio más famoso de su época. Su configuración dispone de miles de millones de combinaciones, lo que en realidad es quedarse corto. De hecho, hay más de 43 trillones (4.3252 x 10¹⁹) de estados diferentes que pueden alcanzarse con cualquier configuración dada.