The famous chess problem that no computer can solve
A popular chess problem, the Queen’s Puzzle, has been plaguing mathematicians, chess players, and computer scientists for decades and decades, although no one has found an algorithm that can solve it easily and efficiently.
British researchers have even come out and told us recently that no computer will ever succeed, offering a $ 1 million reward to anyone who proves they are wrong!
The puzzle has existed since the 1850s and causes us to place 8 queens on a chessboard so that none of them can attack the other.
The chess problem has been solved by humans, as 92 solutions have been proposed out of 4,426,166,368 possible combinations of the 8 queens on the black and white chessboard, although both mathematicians and computer scientists cannot find a magic and fast formula.
As the chessboard grows larger and more queens are placed, it becomes much more difficult, according to a study published in The Journal of Artificial Intelligence Research, which claims that it is virtually impossible for a computer to solve it in a reasonable amount of time. space!
“Computationally costly” they call it, as a 27×27-squared chessboard has 2.34sqm of possible solutions. When the chessboard reaches 1,000×1,000 squares and the computer has to place 1,000 queens, it disappears into the abyss of crazy big numbers.
As head of research and university professor Ian Gent tells us, every computer (even legendary supercomputers) would take thousands of years to find the most cost-effective solution and the researcher is ready to bet $ 1 million on it! Amount actually offered by the American Clay Mathematics Institute.
Gent tells us that anyone who manages to solve the Queen’s Puzzle with a program will then have a powerful algorithm that can handle other almost impossible problems of humanity, such as decoding the most serious cryptographers. He insists, however, that the cheese is this “very fast” as it wants from the machines.
Which seems to fail where chess players do empirically …