Los científicos están ofreciendo un premio de US $ 1 millón a cualquiera que pueda resolver un clásico problema diabólicamente complicado de ajedrez conocido como Puzzle de la Reina y conseguir que un programa de computadora lo resuelva también.
La belleza del desafío es que ni siquiera realmente se necesita conocer las reglas del ajedrez para participar, pero eso no significa que será fácil. De hecho, los investigadores dicen que la solución es matemáticamente tan compleja que encontrar que podría tomar miles de años
El profesor de Ciencias de la Computación Ian Gent y sus colegas de la Universidad de St. Andrews han retado inclusive a los programadores de computación de cualquier lugar del mundo a crear un programa capaz de resolver este famoso rompecabezas de ajedrez, un desafío que, según explican los especialistas, inclusive un ordenador podría tardar miles de años en acabar.
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.
Para poner las cosas en contexto, entonces, vamos a empezar por el principio.
El rompecabezas de la reina (aka el rompecabezas de ocho reinas), fue publicado originalmente en 1848, y consiste en la colocación de ocho reinas en un tablero de ajedrez 8 x 8, de tal manera que nunca dos reinas se amenacen directamente una a otra.
Quien conozca las reglas del ajedrez, sabrá que la reina es la pieza más poderosa en el tablero, ya que puede moverse en ocho direcciones: arriba, abajo, lado a lado y en diagonal. Y eso no es todo ya que la reina también puede moverse una distancia ilimitada en cualquiera de estas direcciones.
Esa libertad sin precedentes de movimiento es la razón por la que el Puzzle de la Reina es un desafío seductor para los jugadores de ajedrez y los matemáticos.
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.
De hecho, hay 92 maneras diferentes de resolver el rompecabezas – de unos 4.500 millones de arreglos potenciales de las ocho reinas en el tablero – por lo que los matemáticos han buscado por mucho tiempo hacer las cosas más interesantes.
«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.
El problema puede ser fácil de comprender en su mente, pero averiguar formas de resolver eficientemente el rompecabezas es en realidad uno de los desafíos más difíciles en complejidad computacional.
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.