Hace pocas fechas ha sido noticia el famoso cubo de Rubik por haberse descubierto el denominado “algoritmo de Dios”. Una buena ocasión para hacer un poco de historia sobre un rompecabezas con el que casi todos hemos intentado alguna vez hacer coincidir los colores del cubo “mágico” y la mayoría, al darnos cuenta de su dificultad, lo hemos dejado y nos hemos dedicado a otra cosa.
El cubo de Rubik se convirtió en los años ochenta en uno de los juegos de entretenimiento más populares. Fue inventado en Hungría, en 1974, por Ernö Rubik, un escultor y profesor de arquitectura. Aunque se puso a la venta en 1977, su verdadero lanzamiento comercial se produjo en 1980 y hasta hoy se han vendido más de 400 millones de unidades. De hecho se ha convertido en el juguete más vendido de todos los tiempos y está considerado por muchos como el mejor puzzle existente.
En su diseño original, conocido por “Cubo de Rubik” 3x3x3, las 6 caras del cubo están divididas en 9 cuadrados de un mismo color que se pueden cambiar de posición mediante rotación de sus secciones. Está formado por un total de 27 piezas o pequeños cubos que se articulan entre sí a través de un mecanismo central oculto en el interior del cubo. El objetivo del juego consiste en, partiendo de un cubo desordenado, lograr que todos los cuadrados de cada cara tengan el mismo color.
El número de estados o posiciones del que se puede partir es impresionante. Según Wikipedia, donde se puede encontrar la demostración matemática, existen 43.252.003.274.489.856.000 permutaciones posibles (más de 43 trillones de posiciones). Al inicio nadie se planteó cuantos movimientos harían falta para resolverlo pero en 1995 se descubre que para una posición determinada, llamada “superflip”, se necesitan al menos 20. En ese momento, se comienza a investigar y es cuando aparece el término “número o algoritmo de Dios”, forma con que los expertos llaman al número máximo de movimientos necesario para resolver de forma óptima un cubo tradicional de 3×3×3 en cualquiera de sus posiciones de partida.
Por la gran complejidad de su cálculo, el principio que guió la investigación fue la idea de que si Dios jugara a un puzzle como éste, utilizaría su capacidad para saberlo todo (omnisciencia) y aplicaría el camino más corto para su resolución. Al comienzo de la búsqueda se pensó que el “algoritmo de Dios” podría estar entre 18 y 80 para las posiciones iniciales más difíciles. Al poco tiempo, las universidades más prestigiosas se interesan por la resolución del problema y, mediante el empleo de algoritmos y técnicas informáticas, el número de movimientos necesarios se ha ido reduciendo en las últimas décadas hasta que este año el final del misterio ha quedado desentrañado.
En 1981, Morwen Thistlethwaite, profesor de Matemáticas de la Universidad de Tennessee, concluyó que el juego podía resolverse en 52 movimientos. Investigaciones posteriores fueron bajando el número, hasta que en 1995 Michael Reid redujo drásticamente la cifra y la situó en 29. Más tarde se conjeturó con que el “número de Dios” estaría entre 20 y 29. En 1997 ya se pensaba que se podría bajar de 27 pero la búsqueda no tenía los frutos esperados, pero un trabajo en el año 2007 de Gene Cooperman y Dan Kunkle (investigadores de la Universidad Northeastern de Boston (EEUU), con la ayuda del superordenador de su facultad, estableció el nuevo listón en 26 movimientos. En 2008, el matemático Tomas Rokicki demostró, con sus estudios en la universidad de Stanford (EEUU), que el cubo mágico se podía resolver en solo 25 movimientos y lo fue bajando hasta dejarlo más tarde en 22. Finalmente, este mes de julio pasado, un equipo de investigación multidisciplinar en el que estaba el propio Rokicki, ha logrado lo que parece ser la solución definitiva: 20 es el valor del algoritmo de Dios.
El equipo estaba formado por: Morley Davidson, responsable de investigación de la Universidad de Kent en Ohio (EEUU), 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 era resolver las 43.252.003.274.489.856.000 (más de 43 trillones) posiciones posibles, clasificándolas en 2.217.093.120 de conjuntos (más de 2.200 millones), cada uno con 20.000 millones de posiciones distintas. Su estrategia consistió en reducir este grupo, mediante la consideración de simetrías (de colores y rotaciones del cubo), a ¡¡solo¡¡ 55.882.296 de conjuntos (casi 56 millones de posibles combinaciones). Pero seguía siendo una cifra muy alta por la enorme cantidad de tiempo que requerirían los ordenadores normales para su interpretación. Es entonces cuando deciden recurrir a Google, cuya ayuda sería determinante en esta titánica tarea, que les cede, además de uno de sus ingenieros, parte de sus superordenadores con los que hicieron el trabajo equivalente a 35 años de un ordenador convencional. Al final, los investigadores se mostraron convencidos de que 20 era el “número de Dios” ya que las opciones de solucionarlo en más movimientos “cayeron a dígitos mínimos”. Ver toda la información técnica en http://www.cube20.org/.
Otro aspecto muy interesante del cubo de Rubik, pero lejos de la teoría matemática, son las competiciones de los speedcubers, como se denomina a las personas aficionadas a resolver el cubo de la forma más rápida posible. Aunque nunca fue concebido para competir, el reto era resolverlo, su interés ha suscitado que se organicen muchas competiciones en busca de la solución más rápida. El primer torneo internacional lo organizó Guinness de los récords, y se llevó a cabo en Munich en 1981. El ganador oficial, con una marca de 38 segundos, fue Jury Froeschl, nacido en Munich. El primer campeonato mundial tuvo lugar en Budapest el en 1982, y lo ganó Mihn Thai, un estudiante vietnamita de Los Ángeles con un tiempo de 22.95 segundos. Desde entonces las sedes de Toronto (Canadá) Orlando (EEUU) y Budapest (Hungría) han organizado el evento, que se celebra regularmente cada dos años. La destreza manual es tal que se alcanzan cifras tan asombrosas como tiempos «sub-10»: cubos resueltos en menos de diez segundos. La World Cube Association es la que mantiene el registro de los récords mundiales, siendo el neerlandés Erik Akkersdijk quien ostenta el récord actual con un tiempo de 7,08 segundos. Existe una Web oficial donde se puede ver como han ido mejorando estos tiempos: Récords mundiales y por países.
En España, el nivel ha subido mucho en estos últimos años, y existen varios speedcubers que empiezan a destacar a escala internacional. Además del campeonato nacional absoluto que se disputa de forma regular desde hace tiempo, se celebró hace poco el primer Campeonato Escolar con 15 colegios participantes.
El cubo de Rubik plantea un problema apasionante en el campo de la inteligencia artificial. Tal es su fuerza que hace poco el diseñador alemán Konstantin Datz ha creado un cubo dirigido a las personas con graves problemas de visión, en el que los colores de las caras han sido sustituidos por sus equivalentes en código Braille. No cabe duda que para muchos este juguete ha pasado de ser un simple pasatiempo a una verdadera obsesión.
El cubo de Rubik se convirtió en los años ochenta en uno de los juegos de entretenimiento más populares. Fue inventado en Hungría, en 1974, por Ernö Rubik, un escultor y profesor de arquitectura. Aunque se puso a la venta en 1977, su verdadero lanzamiento comercial se produjo en 1980 y hasta hoy se han vendido más de 400 millones de unidades. De hecho se ha convertido en el juguete más vendido de todos los tiempos y está considerado por muchos como el mejor puzzle existente.
En su diseño original, conocido por “Cubo de Rubik” 3x3x3, las 6 caras del cubo están divididas en 9 cuadrados de un mismo color que se pueden cambiar de posición mediante rotación de sus secciones. Está formado por un total de 27 piezas o pequeños cubos que se articulan entre sí a través de un mecanismo central oculto en el interior del cubo. El objetivo del juego consiste en, partiendo de un cubo desordenado, lograr que todos los cuadrados de cada cara tengan el mismo color.
Interior del cubo de Rubik con su mecanismo central oculto
El número de estados o posiciones del que se puede partir es impresionante. Según Wikipedia, donde se puede encontrar la demostración matemática, existen 43.252.003.274.489.856.000 permutaciones posibles (más de 43 trillones de posiciones). Al inicio nadie se planteó cuantos movimientos harían falta para resolverlo pero en 1995 se descubre que para una posición determinada, llamada “superflip”, se necesitan al menos 20. En ese momento, se comienza a investigar y es cuando aparece el término “número o algoritmo de Dios”, forma con que los expertos llaman al número máximo de movimientos necesario para resolver de forma óptima un cubo tradicional de 3×3×3 en cualquiera de sus posiciones de partida.
Por la gran complejidad de su cálculo, el principio que guió la investigación fue la idea de que si Dios jugara a un puzzle como éste, utilizaría su capacidad para saberlo todo (omnisciencia) y aplicaría el camino más corto para su resolución. Al comienzo de la búsqueda se pensó que el “algoritmo de Dios” podría estar entre 18 y 80 para las posiciones iniciales más difíciles. Al poco tiempo, las universidades más prestigiosas se interesan por la resolución del problema y, mediante el empleo de algoritmos y técnicas informáticas, el número de movimientos necesarios se ha ido reduciendo en las últimas décadas hasta que este año el final del misterio ha quedado desentrañado.
En 1981, Morwen Thistlethwaite, profesor de Matemáticas de la Universidad de Tennessee, concluyó que el juego podía resolverse en 52 movimientos. Investigaciones posteriores fueron bajando el número, hasta que en 1995 Michael Reid redujo drásticamente la cifra y la situó en 29. Más tarde se conjeturó con que el “número de Dios” estaría entre 20 y 29. En 1997 ya se pensaba que se podría bajar de 27 pero la búsqueda no tenía los frutos esperados, pero un trabajo en el año 2007 de Gene Cooperman y Dan Kunkle (investigadores de la Universidad Northeastern de Boston (EEUU), con la ayuda del superordenador de su facultad, estableció el nuevo listón en 26 movimientos. En 2008, el matemático Tomas Rokicki demostró, con sus estudios en la universidad de Stanford (EEUU), que el cubo mágico se podía resolver en solo 25 movimientos y lo fue bajando hasta dejarlo más tarde en 22. Finalmente, este mes de julio pasado, un equipo de investigación multidisciplinar en el que estaba el propio Rokicki, ha logrado lo que parece ser la solución definitiva: 20 es el valor del algoritmo de Dios.
El equipo estaba formado por: Morley Davidson, responsable de investigación de la Universidad de Kent en Ohio (EEUU), 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 era resolver las 43.252.003.274.489.856.000 (más de 43 trillones) posiciones posibles, clasificándolas en 2.217.093.120 de conjuntos (más de 2.200 millones), cada uno con 20.000 millones de posiciones distintas. Su estrategia consistió en reducir este grupo, mediante la consideración de simetrías (de colores y rotaciones del cubo), a ¡¡solo¡¡ 55.882.296 de conjuntos (casi 56 millones de posibles combinaciones). Pero seguía siendo una cifra muy alta por la enorme cantidad de tiempo que requerirían los ordenadores normales para su interpretación. Es entonces cuando deciden recurrir a Google, cuya ayuda sería determinante en esta titánica tarea, que les cede, además de uno de sus ingenieros, parte de sus superordenadores con los que hicieron el trabajo equivalente a 35 años de un ordenador convencional. Al final, los investigadores se mostraron convencidos de que 20 era el “número de Dios” ya que las opciones de solucionarlo en más movimientos “cayeron a dígitos mínimos”. Ver toda la información técnica en http://www.cube20.org/.
Otro aspecto muy interesante del cubo de Rubik, pero lejos de la teoría matemática, son las competiciones de los speedcubers, como se denomina a las personas aficionadas a resolver el cubo de la forma más rápida posible. Aunque nunca fue concebido para competir, el reto era resolverlo, su interés ha suscitado que se organicen muchas competiciones en busca de la solución más rápida. El primer torneo internacional lo organizó Guinness de los récords, y se llevó a cabo en Munich en 1981. El ganador oficial, con una marca de 38 segundos, fue Jury Froeschl, nacido en Munich. El primer campeonato mundial tuvo lugar en Budapest el en 1982, y lo ganó Mihn Thai, un estudiante vietnamita de Los Ángeles con un tiempo de 22.95 segundos. Desde entonces las sedes de Toronto (Canadá) Orlando (EEUU) y Budapest (Hungría) han organizado el evento, que se celebra regularmente cada dos años. La destreza manual es tal que se alcanzan cifras tan asombrosas como tiempos «sub-10»: cubos resueltos en menos de diez segundos. La World Cube Association es la que mantiene el registro de los récords mundiales, siendo el neerlandés Erik Akkersdijk quien ostenta el récord actual con un tiempo de 7,08 segundos. Existe una Web oficial donde se puede ver como han ido mejorando estos tiempos: Récords mundiales y por países.
En España, el nivel ha subido mucho en estos últimos años, y existen varios speedcubers que empiezan a destacar a escala internacional. Además del campeonato nacional absoluto que se disputa de forma regular desde hace tiempo, se celebró hace poco el primer Campeonato Escolar con 15 colegios participantes.
El cubo de Rubik plantea un problema apasionante en el campo de la inteligencia artificial. Tal es su fuerza que hace poco el diseñador alemán Konstantin Datz ha creado un cubo dirigido a las personas con graves problemas de visión, en el que los colores de las caras han sido sustituidos por sus equivalentes en código Braille. No cabe duda que para muchos este juguete ha pasado de ser un simple pasatiempo a una verdadera obsesión.
