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