The N Queens problem was recognized as an NP-complete problem.


    First Embodiment puzzle 1850, when two queens pre-installed on the board, and the player has to arrange other queens (two solutions problem cm. Under the cut)

    Problem of N queens is to place N queens on the board size N × N thus so that no queen is under the battle of another, while several queens are set in advance on the board. 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 at the University of St. Andrews (Scotland) have published a scientific articlein which they prove that the problem of N queens is not only a # P-complete problem, but also an NP-complete problem. 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 the 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 attracted 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 recognized four of them to be 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 variant of the problem, that is, the determination of the number of solutions for N queens, is the sequence A000170from 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 . It is not known any more effective solution of a problem, than simple search. 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 extract 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. “These include 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:


    Also popular now: