El ‘Rompecabezas de las Reinas’ es un sencillo y, a la vez, complejo, acertijo de ajedrez, que fue concebido en 1850. Consiste en colocar ocho reinas en un tablero de ajedrez grande, no el estándar, y que dos reinas no se ataquen entre sí.
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.
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».
Aún así quien consiga resolver el acertijo será recompensado con un premio de un millón de dólares por parte del Clay Mathematics Institute en América.
«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», ha dicho Jefferson.
