Resolución del cubo de Rubik en 26 movimientos

Gene Cooperman y su colaborador Dan Kunkle, ambos de Northeastern University, consiguen demostrar que con 26 movimientos o menos es posible resolver el cubo de Rubik desde cualquier configuración inicial. La anterior marca mundial estaba en 27 movimientos.

El cubo de Rubik representa más que un juego o un entretenimiento para los expertos en ciencias de la computación y matemáticos, ya que les permite comprobar y comparar estrategias para la obtención de algoritmos que resuelvan problemas de búsqueda y enumeración. Este tipo de problemas se dan en muchas disciplinas que incluyen la inteligencia artificial.

Para lograr esta nueva marca los investigadores citados usaron dos técnicas principalmente: un sistema de 7 terabytes en discos duros como extensión de memoria RAM para mantener grandes tablas de datos y un nuevo sistema de computación de movimientos o conjunto de movimientos muy rápido basado en el uso de teoría de grupos (una rama de las matemáticas).

Cooperman y Kunkle colocaron todas las posibles configuraciones del cubo de Rubik en una familia de conjuntos de configuraciones (denominada coset en teoría de grupos). Entonces miraban el resultado cuando se aplicaba un movimiento simple sobre todas las configuraciones a la vez de un coset. Entonces simularon esto en una computadora a un ritmo de 100 millones de veces por segundo usando una nueva técnica de teoría de grupos.

Richard Korf (de UCLA) anunció en mayo de 1997 que había encontrado la primera solución óptima al cubo de Rubik. Su investigación mostraba que la solución óptima media constaba de 18 movimientos. Además él creía que el cubo se podía resolver en menos de 20 movimientos. Sin embargo, fue incapaz de demostrar tal afirmación, aunque sí probó que como mínimo se podría resolver con 27 movimientos.

El programa de Korf gastaba mucho tiempo en encontrar la solución óptima para estados simples de partida, pero en esta nueva aproximación de Cooperman el ordenador hace primero una precomputación y después, de forma muy rápida (en un segundo) encuentra una solución en 26 movimientos o menos para cualquier estado o configuración de partida del cubo. Para este cálculo Cooperman y Kunkle usaron ordenadores del Teragrid (teragrid.com) y de su propia universidad.

El cubo de Rubik fue inventado al final de los años setenta y probablemente es el rompecabezas combinatorio más famoso, pudiendo adoptar un ingente número de combinaciones, concretamente 4,3252 × 1019 configuraciones posibles.
Fuente: Northeastern University.