Búsqueda de Temas

sábado, 18 de agosto de 2007

Resuelven Cubo de Rubik en solo 26 movimientos

Ya es oficialmente posible resolver el famoso cubo Rubik en sólo 26 movimientos, en lugar de los 27 que constituían el último récord. La nueva hazaña (equivalente matemático del paso en la Luna que era pequeño para el astronauta Neil Armstrong, pero enorme para la Humanidad) se debe a Daniel Kunkle y Gene Cooperman, dos investigadores informáticos de la Universidad de Boston.

Gracias a su «hallazgo» se convirtieron en las estrellas del reciente simposio de computación simbólica y algebráica en la provincia canadiense de Ontario. En una ciudad llamada Waterloo.

El dichoso cubo, que primero se llamó mágico y después Rubik en honor de su creador, el escultor y arquitecto húngaro Erno Rubik, lleva desde 1974 acaparando premios de diseño, ganando dinero, y dando deliciosos quebraderos de cabeza a los matemáticos de todo el mundo. Con sus 54 facetas de brillantes colores en total, 9 por cada una de las 6 caras del cubo, una vez rota la unidad de color de las caras, las configuraciones posibles se elevan a no menos de 43 quintillones. Un abismo donde la fuerza bruta del cálculo se estrella sin remedio, incluso apoyándose en los más poderosos superordenadores.

«Dividir» el problema

Decía el viejo Descartes que si tienes un problema muy grande, hay que intentar dividirlo en problemas más pequeños. Kunkle y Cooperman le hicieron caso. Empezaron por eliminar todas las configuraciones conocidas del cubo que resultaban matemáticamente equivalentes. Por ejemplo, el cubo queda igualmente resuelto si al final la cara de color azul es la dos o la tres. Sólo una de cada posibilidad equivalente entraría en el bombo del análisis.

El segundo paso para estrechar el problema fue considerar sólo configuraciones del cubo que se pudieran resolver con 13 o menos medias vueltas. Hay 15.000 configuraciones así. Empezaron entonces a trabajar para meter todas las demás configuraciones a través de este «cuello de botella».

Reduciendo posibilidades

Calculando, calculando, alternando técnicas de segmentación de la información con multiplicación rápida, Kunkle y Cooperman lograron rebajar los 43 quintillones iniciales a 1.4 trillones. Lo cual seguían siendo cifras mayores.
Después de mucho amor, mucha técnica y de 63 horas de computación frenética, las máquinas concluyeron que con un máximo de 16 movimientos era posible reducir cualquier configuración del cubo a una de las elegidas, las que se resuelven en 13 o menos medias vueltas. Eso llevaba los algoritmos a un punto en que se podía garantizar el desenlace de cualquier combinación en 29 pasos.

Pero el reto era bajar de los 27 que Silviu Radu, del Instituto Tecnológico Lund, en Suecia, logró el año pasado. Y aquí entra la picardía matemática del dúo maravilla de Boston: para imponerse a Radu pero sin perderse en cálculos innecesarios, se dedicaron sólo a buscar soluciones de 26 movimientos o más. Eso tenía la ventaja a la vez de simplificar y hacer durar el problema: queda cuerda para rato, para seguir buscando nuevos récords todavía más ajustados.

¿Dónde está el límite? Algunos expertos creen que el número más bajo absoluto de movimientos necesarios para resolver el cubo e Rubik -al que ya llaman el «número de Dios»- se sitúa muy poco por encima de los 20 pasos. Pero la gracia no es creerlo ni decirlo, claro, sino demostrarlo con los algoritmos en la mano. Y, mientras no se demuestre lo contrario, Kunkle y Cooperman tienen la última palabra.

Via: ABC

Contáctame