martes, 17 de agosto de 2010

El numero magico del "Cubo de Rubik"

Hace mucho tiempo, cuando tenía once años, mi madre me regaló un “cubo de Rubik”, un pasatiempo novedoso y popular en esa epoca, ya que ella sabía que me gustaba resolver puzles. Yo pasé unas cuantas horas dándole vueltas y vueltas a los “cubies”, pero no daba pie con bola. Mi primo Juan Luís, en ese entonces un estudiante recién ingresado a la universidad me enseñó un algoritmo sencillo para armar una cara que tenía un principio común al de los puzles de ordenar quince celdillas numeradas en un cuadrado de 4x4: había que deshacer provisionalmente lo avanzado para introducir las mejoras y luego revertir lo deshecho. Para mi esta revelación fue como un salto cuántico, y me sirvió para ir perfeccionando el algoritmo para armar dos caras, luego tres caras…pero la complejidad del procedimiento creció muchísimo. Un día logré armar cuatro caras y las dos restantes estaban casi listas, así que me puse a estudiar las posibles secuencias hasta que se encendió el bombillo y di con una cuantas vueltas que me permitieron resolver el puzle por primera y única vez, ya que hice como Bart Simpson con el video juego de boxeo: Decidí retirarme en mi mejor momento.



Un par de años después, vi un programa de TV en el que los participantes competían con el dichoso cubo, para ver quien lo resolvía en el menor tiempo posible. La velocidad de los participantes era asombrosa, y llegué a la conclusión de que la técnica de estos muchachos era, comparada con la mía, como un Ferrari comparado con un Ford T. “Tiene que haber un algoritmo más eficiente”, me dije a mi mismo, por lo cual decidí consultar con un amigo muy inteligente que cursaba el último año de bachillerato. Mi amigo me dijo que él tenía un par de libros que exponían métodos para resolver rápidamente el cubo, pero a mí no me interesaba aprender esos métodos sino confirmar mi intuición. Más recientemente, conversando con mi esposa, ella me contó que si se puso a aprender esos algoritmos más eficientes y que en su momento resolvió unas cuantas veces el cubo.

video


Hace unos días estuve surfeando por la web, aprovechando que mi hija recién nacida estaba dormidita, y me topé con una noticia un tanto sorpresiva: se había establecido por fin que el número máximo de movimientos necesarios para resolver el dichoso cubo era de 20. Me pareció un bonito numero, porque coinciden con el numero de cubies que se pueden mover; ya que de los 26 "cubies" (secciones en las que esta dividido el cubo) visibles, los seis del centro de cada cara son inmóviles. Me puse a revisar unas cuantas páginas y me encontré con la historia de la mencionada demostración. Lo que me pareció bien interesante es que el principio que guía la investigación es la idea de que si Dios jugara un puzle como esta, usaría su omnisciencia para hallar el camino más corto posible a su resolución: el llamado “algoritmo de Dios”. Eso me recuerda un cuento: Moisés, Jesús y un viejito misterioso decidieron disputar un juego de golf, y el campo se llenó de fanáticos antes del partido. En el hoyo considerado como el más difícil porque tenía un lago en el medio, Moisés tiró primero. La pelota salió disparada, cayó en el medio del lago y se hundió. Moisés caminó hasta el borde, alzó su palo, hizo que se abrieran las aguas, bajó caminando hasta donde estaba la pelota y, de un golpe, la sacó del fondo. Con sólo otro golpe, la metió en el hoyo, y la gente aplaudió emocionada. Luego fue el turno de Jesús. La pelota salió igualmente disparada, e igualmente fue derecho al lago, pero de repente se detuvo y quedó suspendida a escasos centímetros de la superficie. Jesús caminó entonces sobre las aguas y con un golpe preciso, mandó la pelota directamente al hoyo. Vino el turno del viejito, el cual dio un disparo que también iba directo al centro del lago, pero antes de que tocara el agua un pez saltó y se tragó la pelota, pero antes de que el pez pudiera hundirse, un águila capturó al pez y se alejó volando, pero entonces un rayo pasó cerca del águila, lo cual hizo que soltara al pez y que este a su vez soltara la pelota que cayó justo en el hoyo. Jesús se volteó hacia el viejito y le dijo “¡Creo que te excediste papá!”

Pero volvamos al tema del cubo. Al comienzo del la búsqueda del “numero de Dios”, o el número máximo que el “algoritmo de Dios” tomaría en resolver las posiciones iniciales más difíciles estableció que debía estar entre 18 y 80. Quince años después de la invención del cubo, en 1995, se estableció la primera posición de máxima dificultad que requería exactamente 20 movimientos (la llamada posición “superflip”), al tiempo que se conjeturó que el número de Dios estaría entre 20 y 29. Quince años después, en 2010, se constituyó el equipo que cerró el tema: Morley Davidson, un matemático de la Universidad del Estado de, John Dethridge, un ingeniero de Google en Mountain View, Herbert Kociemba, profesor de matemáticas de Darmstadt, Alemania, y Tomas Rokicki, un programador Palo Alto, California. El reto fue resolver las 43,252,003,274,489,856,000 posiciones posibles, clasificándolas en 2,217,093,120 conjuntos, y mediante una estrategia que consistió en reducir, mediante la consideración de simetrías (de colores y rotaciones del cubo), este grupo a solo (!) 55,882,296 conjuntos. Luego vino la utilización del equivalente a 35 años de computación, cortesía de la empresa Goolge, para poder probar que el número mágico es 20, todo un ejemplo de lo que Claude Shannon llamó "estrategia de la fuerza bruta". (Toda la información técnica está en http://www.cube20.org/)

Aunque me alegra estar viviendo una epoca en la que teoremas como el de Fermat se han demostrado mediante el uso de potentes computadoras y haber visto a un programa de ajedrez derrotar a Kasparov, sigo creyendo que hay una solución muy humana al cubo de Rubik, y que fue publicitada en mi país a finales de los ochenta: darle con un martillo, y rearmalo resuelto de una vez!

2 comentarios:

SATURNINO dijo...

Vaya yo nunca me he visto atraído por el cubito de marras. Cuando cayó el primero en mis manos enseguida vi que era un muro infranqueable y no decidí darme de cabezazos contra él.
Sólo lo he logrado hacer una vez, y no fue con el martillo (salvajes!!) lo mío fue un método más fino: cambiarle las pegatinas, jeje

euge dijo...

yo también el cambiaba las pegatinas, jejeje