Here’s a good challenge for family developers with creating algorithms. On Thursday, 31st, the University of St. Andrews in Scotland and the Clay Mathematics Institute in the United States teamed up to announce a $ 1 million prize pool. To win, just create a solution to solve a problem involving the game of chess.
Obviously, if the premium is at that level, it’s because the solution is not simple. However, it is quite easy to understand the problem. Imagine a conventional 8×8 chess board. You have 8 queens. How would you distribute them on the board in such a way that it is impossible, by the rules of game movement, that one piece is unable to attack the other? This is the “problem of the eight queens,” devised in 1850.
This mathematical problem already has a solution when we talk about a conventional 8×8 board. However, when the concept is expanded to much larger trays (think of something 1,000×1,000 with 1,000 pieces, and so on), the solution becomes exponentially more complex. For this reason, researchers believe that computer software would take at least a millennium to solve the problem. And that’s where the competitors come in.
Professor Ian Gent, one of the authors of the challenge, explained to Digital Trends what the competitors’ participation in the game was. There are two ways to earn a million dollars: the first is to prove why no algorithm is able to solve the n-queens problem in a short period of time, or create the algorithm that can solve the problem.
According to him, finding an efficient method of solving the problem is “probably the hardest thing to do in computer science,” and the reason behind this difficulty is that the simplest method is to use brute force to solve the problem by trial and error, which involves analyzing the feasibility of each of the alternatives. When the board has an immense number of houses, as in the 1000×1000 example, testing each of the alternatives becomes an exercise that depends on colossal amounts of time. The algorithm’s mission is to find a smarter way to do such calculations.
What are the requirements to participate in the contest? There is none, besides being a lucky genius. Gent gives three tips to anyone who meets the challenge: have a doctorate in computational complexity, be bright and be lucky.
The challenge goes beyond a mere theoretical problem without any practical application. If solved, the researchers believe that an algorithm capable of solving the queens problem could also solve other problems considered impossible involving cryptography, with many practical applications; one of them would be, for example, making Internet browsing more secure and difficult to intercept.