The N Queens problem was recognized as an NP-complete problem.
The first version of the puzzle of 1850, when two queens are set on the board in advance, and the player must place the rest of the queens (for two solutions of the problem, see under the cut)
The task of N queens is to place N queens on an N × N board in such a way that no queen is under attack of the other, while several queens are set on the board beforehand. That is, in the end, no two queens should be on the same line or diagonal. For the first time, the puzzle was formulated in 1848, and in 1850 a variant of the puzzle was invented, when a certain number of queens were put on the board in advance, and the player must arrange the rest, if possible.
Researchers from the University of St. Andrews (Scotland) have published a scientific article in which they prove that the N Queens problem is not only a # P-complete task, but also an NP-complete task. Moreover, the Clay Mathematical Institute (USA) is ready to pay a million dollars to anyone who can optimize the solution of this problem as a proof problem P = NP.
As is known, in the theory of complexity, #P is a class of problems whose solution is the number of successful, that is, terminating in admitting states, computation paths for a certain non-deterministic Turing machine operating in polynomial time. Computational problems of the class #P (counting problems) are associated with the corresponding problems of solvability (decision problems) of the class NP.
Scientists note that this task may be the simplest among NP-complete tasks, in order to explain the essence of these problems to anyone who knows the rules of the game of chess. This task has a very interesting story. At one time, she caught the attention of Gauss, who even made a small mistake in her decision (on the 8 × 8 board he reported 76 decisions, but then he himself acknowledged four of them were wrong, so only 72 remained, and later Gauss found all 92 decisions for a board of 8 × 8).
The generalization of the task for the N × N board attracted the attention of many mathematicians. Over the past half century, several dozen scientific works devoted to this problem have been published. At least six of them are cited more than 400 times on Google Scholar: this is Golomb & Baumert, 1965; Bitner & Reingold, 1975; Mackworth & Freuder, 1985; Minton, Johnston, Philips, & Laird, 1992; Selman, Levesque & Mitchell, 1992; Crawford, Ginsberg, Luks, & Roy, 1996.
The complexity of the N Queens problem is often incorrectly estimated. Even in abundantly cited works, it is often called an NP-hard problem (NP-hard), but it will be such only if P = NP. In fact, the computational version of the problem, that is, the determination of the number of solutions for N queens, is the A000170 sequence from the Online Encyclopedia of Integer Sequences. This sequence is now known for a maximum of n = 27, where the number of solutions exceeds 2.34 × 10 17 . No more effective solution to the problem is known than simple brute force. So, for n = 27 in 2016, a large-scale parallel search on FPGA was used.
At the same time, if the computer begins to enumerate the possible positions of queens on a board of 1000 × 1000 cells, it will be loaded with this task forever. According to scientists, if someone finds a really fast and effective way to solve it, then he will be able to benefit from this much greater benefit than one million dollars from the Clay Institute of Mathematics. “If you write a program that can solve a problem really quickly, you could adapt it to solve many important tasks that we face daily,” said computer science professor Ian Gent, one of the authors of the scientific work. “Among them are trivial problems, such as finding the largest group of your Facebook friends who don't know each other, or very important tasks, such as hacking codes that ensure the security of all our online transactions.”
But this is purely theoretical speculation. In practice, no one has yet come close to solving the problem of N Queens in a fast and efficient way. For proof that there is a more effective way to solve a problem than to simply search through all the options, they will give a million dollars.
The scientific article was published in August 2017 in the Journal of Artificial Intelligence Research (doi: 10.1613 / jair.5512, pdf ).
PS Two solutions to the problem with KDPV:
All Articles