Selecciona Edición
Entra en EL PAÍS
Conéctate ¿No estás registrado? Crea tu cuenta Suscríbete
Selecciona Edición
Tamaño letra
Reportaje:

Asedio al cubo de Rubik

Dos investigadores y un superordenador resuelven el 'puzzle' en 26 pasos

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á).

* Este artículo apareció en la edición impresa del Sábado, 18 de agosto de 2007