Million-dollar checkmate

One of humanity's oldest games, chess challenges competitors with problems that, at first glance, seem simple, but can take more than a century to solve.

The solution to one of the seven Millennium Problems (P versus NP) has resurfaced after professors at the University of St Andrews (Scotland) published an article reporting that current programmers are unable to find all the solutions to the problem.

Thus, the Clay Mathematics Institute is once again offering US$1 million (R$3.2 million) to whoever solves this 'simple' chess puzzle, which consists of placing 1,000 queens on a 1,000 x 1,000 square chessboard without capturing each other. In short: there cannot be two queens in the same row, column, and diagonal.

Intriguing, the challenge captivated scientists who have been trying for years to create an algorithm capable of generating all the solutions to the enigma. What no one expected was that the article " Complexity of n-Queens Completion ," from the University of St Andrews, would bring bad news for those who have been searching for the solution.

The origin of the problem is the so-called eight queens problem, proposed in 1848 by the German chess player Max Bezzel. The objective was to place eight queens on a standard (8×8) chessboard without the pieces threatening each other. Although complex, the problem was solved two years later by the blind mathematician Franz Nauck, whose solution has 92 options: 12 basic solutions and 80 obtained through rotations and symmetries.

The fact is that, as the chessboard and the number of queens increase, so does the number of solutions, making the P versus NP puzzle more difficult to solve. According to Scottish researchers, when the chessboard is equal to or greater than 1,000 x 1,000, it is impossible to find all the solutions to the problem because there are so many possibilities that current programs would take years just to consider the answers, generating "backtracking," that is, a phenomenon where the program code goes back until a solution is found.

Although it is a mathematical problem, its solution would bring benefits to other areas. If they manage to create it, this superprogram could be adapted to solve the design of microchips and even decipher internet security systems.

According to Peter Nightingale, one of the authors of the article, the solution to the eight queens problem, and consequently to the P versus NP enigma, is far from being achieved. "For all practical purposes, it cannot be done," he asserts.