La primera versión del rompecabezas en 1850, cuando dos reinas están preinstaladas en el tablero, y el jugador debe organizar las reinas restantes (para dos soluciones al problema, ver debajo del corte)La tarea de N queens es colocar N queens en un tablero N × N para que ninguna reina esté bajo la batalla del otro, con varias reinas preinstaladas en el tablero. Es decir, al final, no deben haber dos reinas en la misma línea o diagonal. El problema se formuló por primera vez en 1848, y en 1850 se les ocurrió una variante de rompecabezas, cuando un cierto número de reinas se pusieron en el tablero de antemano, y el jugador debería organizar el resto, si es posible.
Investigadores de la Universidad de St Andrews (Escocia) han publicado un
artículo científico que demuestra que el problema de N-Queens no es solo # P-completo, sino también NP-completo. Además, el Clay Institute of Mathematics (EE. UU.) Está listo para pagar un millón de dólares a cualquiera que pueda optimizar la solución de este problema como un problema de prueba P = NP.
Como saben, en la teoría de la complejidad, #P es una clase de problemas cuya solución es la cantidad de éxitos, es decir, completar en estados de admisión, rutas computacionales para alguna máquina de Turing no determinista que opera en tiempo polinomial. Los problemas computacionales de la clase #P (problemas de conteo) están relacionados con los problemas de decisión correspondientes de la clase NP.
Los científicos señalan que esta tarea puede ser la más simple entre las tareas completas de NP para explicar la esencia de estos problemas a cualquiera que conozca las reglas del juego del ajedrez. Esta tarea tiene una historia muy interesante. En un momento, atrajo la atención de Gauss, quien incluso cometió un pequeño error en su decisión (en el tablero 8 × 8, informó 76 decisiones, pero luego reconoció cuatro de ellas erróneas, por lo que solo quedaron 72, y más tarde Gauss estableció las 92 decisiones para un tablero de 8 × 8).
Una generalización del problema para el tablero N × N ha llamado la atención de muchos matemáticos. Durante el último medio siglo, se han publicado varias docenas de artículos científicos dedicados a este problema. Al menos seis de ellos se citan más de 400 veces en Google Scholar: esto es Golomb y Baumert, 1965; Bitner y Reingold, 1975; Mackworth y Freuder, 1985; Minton, Johnston, Philips y Laird, 1992; Selman, Levesque y Mitchell, 1992; Crawford, Ginsberg, Luks y Roy, 1996.
La complejidad del problema de N-Queens a menudo se juzga mal. Incluso en trabajos abundantemente citados, a menudo se le llama un problema NP-hard (NP-hard), pero será así solo si P = NP. De hecho, la versión computacional del problema, es decir, la determinación del número de soluciones para N reinas, es una
secuencia A000170 de la Enciclopedia en línea de
secuencias enteras . Esta secuencia ahora se conoce como máximo para n = 27, donde el número de soluciones excede 2.34 × 10
17 . No se conoce una solución más efectiva al problema que la simple búsqueda exhaustiva. Entonces, para n = 27 en 2016, se utilizó una búsqueda paralela a gran escala en FPGA.
Al mismo tiempo, si la computadora comienza a enumerar las posibles posiciones de las reinas en una placa celular de 1000 × 1000, cargará esta tarea para siempre. Según los científicos, si alguien encuentra una forma realmente rápida y efectiva de resolverlo, podrá beneficiarse de él por mucho más de un millón de dólares del Clay Institute of Mathematics. "Si escribe un programa que puede resolver el problema realmente rápido, podría adaptarlo para resolver muchas tareas importantes que enfrentamos todos los días", dice el profesor de informática Ian Gent, uno de los autores del trabajo científico. "Entre ellos hay problemas triviales, como encontrar el grupo más grande de amigos en Facebook que no se conocen, o tareas muy importantes, por ejemplo, piratear códigos que garantizan la seguridad de todas nuestras transacciones en línea".
Pero estas son fabricaciones puramente teóricas. En la práctica, nadie ha abordado aún la solución del problema de las N reinas de una manera rápida y efectiva. Para demostrar que hay una forma más efectiva de resolver el problema que una simple enumeración de todas las opciones, darán un millón de dólares.
En agosto de 2017 se
publicó un artículo científico en la revista
Journal of Artificial Intelligence Research (doi: 10.1613 / jair.5512,
pdf ).
PS Dos soluciones al problema con KDPV:
