La première version du puzzle en 1850, lorsque deux reines sont préinstallées sur le plateau, et le joueur doit disposer les reines restantes (pour deux solutions au problème, voir sous la coupe)La tâche de N reines est de placer N reines sur un plateau N × N afin qu'aucune reine ne soit sous la bataille de l'autre, avec plusieurs reines préinstallées sur le plateau. C'est-à-dire qu'au final, il n'y a pas deux reines sur la même ligne ou diagonale. Le problème a été formulé pour la première fois en 1848, et en 1850, ils ont proposé une variante de puzzle, lorsqu'un certain nombre de reines ont été placées à l'avance sur le plateau, et le joueur devrait organiser le reste, si possible.
Des chercheurs de l'Université de St Andrews (Ecosse) ont publié un
article scientifique prouvant que le problème des N-Queens n'est pas seulement # P-complet, mais aussi NP-complet. De plus, le Clay Institute of Mathematics (USA) est prêt à payer un million de dollars à toute personne pouvant optimiser la solution de ce problème comme un problème de preuve P = NP.
Comme vous le savez, dans la théorie de la complexité, #P est une classe de problèmes dont la solution est le nombre de succès, c'est-à-dire, en complétant dans les états d'admission, des chemins de calcul pour une machine de Turing non déterministe fonctionnant en temps polynomial. Les problèmes de calcul de la classe #P (problèmes de comptage) sont liés aux problèmes de décision correspondants de la classe NP.
Les scientifiques notent que cette tâche peut être la plus simple parmi les tâches NP-complètes pour expliquer l'essence de ces problèmes à quiconque connaît les règles du jeu d'échecs. Cette tâche a une histoire très intéressante. À un moment donné, elle a attiré l'attention de Gauss, qui a même fait une petite erreur dans sa décision (sur le tableau 8 × 8, il a signalé 76 décisions, mais il a reconnu quatre d'entre elles erronées, de sorte qu'il n'en restait que 72, et plus tard, Gauss a établi les 92 décisions pour une planche 8 × 8).
Une généralisation du problème pour le tableau N × N a attiré l'attention de nombreux mathématiciens. Au cours du dernier demi-siècle, plusieurs dizaines d'articles scientifiques consacrés à ce problème ont été publiés. Au moins six d'entre eux sont cités plus de 400 fois sur Google Scholar: il s'agit de Golomb & Baumert, 1965; Bitner et Reingold, 1975; Mackworth et Freuder, 1985; Minton, Johnston, Philips et Laird, 1992; Selman, Levesque et Mitchell, 1992; Crawford, Ginsberg, Luks et Roy, 1996.
La complexité du problème des N-Queens est souvent mal évaluée. Même dans les ouvrages abondamment cités, il est souvent appelé un problème NP-difficile (NP-difficile), mais il ne le sera que si P = NP. En fait, la version informatique du problème, c'est-à-dire la détermination du nombre de solutions pour N reines, est une
séquence A000170 de l'Encyclopédie en ligne des séquences entières. Cette séquence est maintenant connue au maximum pour n = 27, où le nombre de solutions dépasse 2,34 × 10
17 . On ne connaît pas de solution plus efficace au problème qu'une simple recherche exhaustive. Ainsi, pour n = 27 en 2016, une recherche parallèle à grande échelle sur FPGA a été utilisée.
Dans le même temps, si l'ordinateur commence à énumérer les positions possibles des reines sur une carte de cellule 1000 × 1000, il chargera cette tâche pour toujours. Selon les scientifiques, si quelqu'un trouve un moyen très rapide et efficace de le résoudre, il pourra en bénéficier bien plus d'un million de dollars du Clay Institute of Mathematics. «Si vous écrivez un programme qui peut résoudre le problème très rapidement, vous pouvez l'adapter pour résoudre de nombreuses tâches importantes auxquelles nous sommes confrontés chaque jour», explique le professeur d'informatique Ian Gent, l'un des auteurs des travaux scientifiques. «Parmi eux, il y a des problèmes triviaux, tels que trouver le plus grand groupe d'amis sur Facebook qui ne se connaissent pas, ou des tâches très importantes, par exemple, briser des codes qui assurent la sécurité de toutes nos transactions en ligne.»
Mais ce sont des fabrications purement théoriques. Dans la pratique, personne n'a encore abordé la solution du problème des N reines de manière rapide et efficace. Pour la preuve qu'il existe un moyen plus efficace de résoudre le problème qu'une simple énumération de toutes les options, ils donneront un million de dollars.
Un article scientifique a été
publié en août 2017 dans la revue
Journal of Artificial Intelligence Research (doi: 10.1613 / jair.5512,
pdf ).
PS Deux solutions au problème avec KDPV:
