Asedio al cubo de Rubik

El cubo de Rubik encierra un enigma casi impenetrable. ?Cu¨¢l es el menor n¨²mero de movimientos necesario para resolverlo? Es decir, para conseguir que cada cara vuelva a ser de un solo color desde cualquier combinaci¨®n desordenada. Hay 43 trillones de configuraciones posibles (un 43 seguido de 18 ceros), as¨ª que no es recomendable intentarlo a mano. Armados con un superordenador y con ingenio, dos investigadores estadounidenses han conseguido probar que con 26 movimientos se puede resolver cualquier desorden del cubo de Rubik.

La soluci¨®n puede conllevar m¨²ltiples aplicaciones, desde avances en la capacidad de los ordenadores hasta mejoras en la programaci¨®n de las salidas y las llegadas de los vuelos de una l¨ªnea a¨¦rea, seg¨²n explica a trav¨¦s del correo electr¨®nico el investigador Daniel Kunkle, coautor del hallazgo junto a Gene Cooperman, estudiante de posgrado y profesor, respectivamente, de la facultad de ciencia computacional de la Northeastern University (Boston, Massachusetts, EE UU).

La soluci¨®n del problema puede comportar mejoras en la programaci¨®n de los vuelos en un aeropuerto

Kunkle y Cooperman han empleado una supercomputadora que ha tardado 63 horas en reconfigurar el rompecabezas que invent¨® el arquitecto h¨²ngaro Ern? Rubik en 1974, y que cuenta con nueve facetas en cada una de sus seis caras.

"Su aplicaci¨®n es crucial en la resoluci¨®n de problemas de optimizaci¨®n combinatoria. Por ejemplo, en la programaci¨®n de los vuelos hay muchos aviones, ciudades y horarios posibles, y lo necesario es encontrar el horario ¨®ptimo para cada uno. Para conseguirlo tienes que examinar muchas posibilidades, similares a las muchas posibles configuraciones del cubo de Rubik", explica Kunkle.

Pero la potencia de c¨¢lculo de las computadoras sigue necesitando el ingenio humano. La cifra astron¨®mica de los 43 trillones es mareante incluso para un superordenador, detalla Kunkle, as¨ª que tuvieron que trazar un plan de trabajo para hacerlo m¨¢s manejable. As¨ª que decidieron encarar el enigma en dos fases. Programaron el supercomputador para llegar a una de unas 15.000 configuraciones medio resueltas, conscientes de que podr¨ªan solucionar cualquiera de esas 15.000 con algunos movimientos m¨¢s. El resultado mostr¨® que cualquier cubo, sin importar lo desordenado que est¨¦, se pod¨ªa resolver en un m¨¢ximo de 29 giros, pero la mayor¨ªa pod¨ªan completarse con con 26 o menos. Luego se centraron en los primeros y los introdujeron en el supercomputador. El ordendor fue capaz de resolverlos todos en 26 movimientos.

El avance supone un peque?o paso m¨¢s (el n¨²mero 27 lo estableci¨® en 2006 Silviu Radu, del Instituto Tecnol¨®gico de Lund, en Suecia) hacia la consecuci¨®n del n¨²mero de Dios, la menor cantidad da movimientos necesarios. "El nombre se eligi¨® porque, supuestamente, un ser omnipotente usar¨ªa el m¨ªnimo n¨²mero de movimientos para solucionar el cubo. Ahora sabemos que este n¨²mero no es menor de 20 y no es mayor de 26", concluye Kunkle.

Los dos estudiantes anunciaron su descubrimiento en el Simposio Internacional sobre Computaci¨®n Simb¨®lica y Algebraica de Waterloo (Ontario, Canad¨¢).