The Reward of $ 1 Million for Anyone Who Solved the Problem Has

Anyone who solves the problem, seeking to rank the runner on the board will be awarded a $ 1 million prize. This is a very complicated problem, to find solutions that can take thousands of years.

Key Facts About Chess

In 1848, the 'posthumous n perfect' puzzle was given and simply found a way to put 8 men on an 8 x 8 chess board so that the soldiers could not eat each other, meaning there was no army. Any post can move according to chess rules. This is a very difficult and complicated thing because in chess, the queen can move 8 directions with any distance.

With the problem on the 8 x 8 chess board, surely you will be able to find some solutions that satisfy the above conditions. In fact, this problem has all 92 solutions offered from 4,426,165,368 different ways of placing the queen.

One of the arrangements for the 8-post problem on the 8 x 8 chess board.

Why Chess Matters

If the number of men and the number of cells on the board increases, the problem will be more complicated. For example, with 27 men on the 27 x 27 board chess board, the total number of possible solutions would be 2.34 * 10 ^ 17 - the number would reach million billion.

Now that we have a problem finding ways to put the rear runner on the board, the bigger the n, the harder it is to find a solution.

Specifically, with n = 1000 and on the chess board 1000 x 1000 cells, according to researchers at the University of St Andrews, this problem is extremely difficult to find the solution even with powerful supercomputers. If the problem has one more requirement: some of the post-larvae are fixed on the board, cannot be moved, and never know when the problem will be solved. And this is exactly the problem that computer scientist Ian Gent and researchers at the University of St Andrews, UK have put a $ 1 million prize to anyone who finds an affordable computer program.

According to Gent, if a computer program can solve the problem of military problems quickly and accurately, it can also solve any problem with similar variables that currently supercomputers are still struggling. Find the solution.

The new study, published in the Journal of Artificial Intelligence, said that if this problem had n = 1,000 queens, then the AI would "give up" completely before the number of endless tests.