Hay un millón de dólares para quien resuelva el popular problema de las 8 damas de ajedrez pero en un tablero de 1.000 × 1.000 con 1.000 damas.
Obviamente no es un problema fácil. El original que todos conocemos se propuso en 1848 con ocho damas y aunque también se han encontrado las soluciones para 9, 10 y hasta 14 damas, no se conoce una forma de dar con una generalización de la solución ni tampoco el caso concreto de 1.000 × 1.000.
Más detalles en El País: Un millón de dólares para quien resuelva este “simple” enigma de ajedrez.
Actualización – José Luis nos hizo llegar un enlace a la fuente original (ClayMath) donde se explica que cuando los autores de un trabajo acerca del problema hablaban de esto podría significar ganar el millón de dólares de los Problemas del milenio no era el caso.
En realidad es un problema del tipo P vs. NP llamado Problema de completitud de las n-Damas, donde se trata de las soluciones de tipo P y NP para un tablero genérico en el que además ya se hayan hecho algunas «jugadas». En sus propias palabras: «sería necesario demostrar que hay un algoritmo que puede resolver el problema de completitud de las n-Damas en tiempo polinomial o una demostración de que no existe dicho algoritmo.»
