EP

  • Expertos en computación y programadores han retado a colegas a resolver un problema de ajedrez que podría tardar miles de años en resolverse.
  • Diseñado en 1850, es conocido como el 'Rompecabezas de las Reinas' y la Clay Mathematics Institute en América ofrece un millón a la persona que lo resuelva.
  • Cualquier persona capaz de resolverlo sería capaz de descifrar las mayores medidas de seguridad en internet.

The 8-Queens Puzzle

Programadores han desafiado a sus colegas a encontrar solución a un 'sencillo' rompecabezas de ajedrez que podría tardar miles de años en resolverse, y obtener un premio de un millón de dólares.

El profesor de Ciencias de la Computación Ian Gent y sus colegas de la Universidad de St. Andrews creen que cualquier programa capaz de resolver eficazmente el famoso 'Rompecabezas de las Reinas' sería tan poderoso que sería capaz de resolver tareas actualmente consideradas imposibles, como descifrar las mayores medidas de seguridad en internet.

En un artículo publicado en Journal of Artificial Intelligence Research, el equipo concluye que las recompensas para ser cosechadas por este programa serían inmensas, no sólo en términos financieros con empresas que se apresuren a utilizarlo para ofrecer soluciones tecnológicas, sino también por el premio de un millón de dólares ofrecido por el Clay Mathematics Institute en América.

Diseñado originalmente en 1850, el 'Queens Puzzle' desafió originalmente a un jugador a colocar ocho reinas en un tablero de ajedrez estándar para que ninguna reina se atacara entre sí. Esto significa poner una reina en cada fila, de modo que no hay dos reinas en la misma columna, y no hay dos reinas en la misma diagonal. Aunque el problema original ha sido resuelto por los seres humanos, una vez que el tablero de ajedrez aumenta a un tamaño grande ningún programa de ordenador puede solucionarlo.

El profesor Gent y sus colegas, el investigador Peter Nightingale y el lector Dr. Christopher Jefferson, todos de la Escuela de Ciencias de la Computación de la Universidad, se sintieron intrigados por el rompecabezas después de que un amigo desafiara al profesor Gent a resolverlo en Facebook.

El equipo encontró que una vez que el tablero de ajedrez alcanzó 1.000 por 1.000 cuadrados, los programas de ordenador ya no podían hacer frente a la gran cantidad de opciones y se hundieron en una lucha potencialmente eterna similar al superordenador ficticio Deep Thought en la obra 'Hitchhiker's Guide to the Galaxy' de Douglas Adams, que tardó siete millones y medio de años en dar una respuesta al significado de todo.

¿Imposible de resolver?

"Si pudieras escribir un programa de ordenador que pudiera resolver el problema realmente rápido, podrías adaptarlo para resolver muchos de los problemas más importantes que nos afectan todos a diario", afirma el profesor Gent.

"Esto incluye desafíos triviales como trabajar con el grupo más grande de tus amigos de Facebook que no se conocen, o muy importantes como romper los códigos que mantienen todas nuestras transacciones en línea seguras", añade.

La razón de que estos problemas sean tan difíciles para los programas de computadora, es que hay tantas opciones a considerar que puede tomar muchos años. Esto se debe a un proceso de backtracking, un algoritmo utilizado en la programación donde se considera cada opción posible y luego se "retrocede" hasta que se encuentra la solución correcta.

"Sin embargo, todo esto es teórico. En la práctica, nadie ha llegado a escribir un programa que pueda resolver el problema rápidamente. En consecuencia, lo que nuestra investigación ha demostrado es que (a todos los efectos prácticos) no puede hacerse", señala Nightingale.

Jefferson agrega que "hay un premio de un millón de dólares para cualquier persona que pueda probar si el Problema de las Ocho Reinas puede ser resuelto rápidamente, por lo que las recompensas son altas".

El ajedrez ha sido durante mucho tiempo la fuente de rompecabezas como la tradicional fábula del sirviente que, cuando le pidieron que escogiera una recompensa por su rey, pidió que un grano de arroz fuera colocado en el primer cuadrado de un tablero de ajedrez estándar de 8x8, doblándolo sucesivamente en cada cuadro hasta que se encontró que no había bastante arroz en el mundo entero.

La fábula indica los grandes números involucrados cuando se usa un tablero de ajedrez de tamaño estándar. Cuando el tamaño del tablero aumenta, los números se vuelven enormes.