El rompecabezas de las reinas del ajedrez que desafía a los programadores

En un artículo publicado en « Journal of Artificial Intelligence Research », el equipo de St. Andrews subraya que si un programa lograra superar 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.

Diseñado originalmente en 1850, el «Queens Puzzle» desafió originalmente a un jugador a colocar ocho reinas en un tablero de ajedrez de tal forma que ninguna reina se atacara entre sí. Esto supone situar una reina en cada fila, de modo que no haya dos reinas en la misma columna, y tampoco 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 mayor, 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ó unas dimensiones de 1.000 por 1.000 cuadrados, los programas de ordenador ya no podían hacer frente a la gran cantidad de opciones y se hundían en una lucha potencialmente eterna.

«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 informáticos, es que son tantas las opciones que hay que considerar que la solución puede tardar 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.

«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.

Aunque la difusión del artículo de Gent y sus colegas ha llevado a pensar a algunos (y así ha salido publicado en muchos medios de comunicación) que quien resolviera el acertijo sería recompensado con un premio de un millón de dólares por parte del Clay Mathematics Institute en América , desde la web del instituto aclaran que si bien sería «una contribución emocionante a la teoría de la complejidad», hallar una solución correcta para el rompecabezas de las ocho reinas o incluso para el de un número indeterminado de reinas en un tablero mayor « no justificaría la concesión del Premio del Milenio » dotado con esta cantidad.

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.