If you have a penchant for problem-solving and love to play chess, then you simply can’t pass up an offer to net $1 Million for doing just that, can you? Folks from the University of St. Andrews and the Clay Mathematics Institute recently came up with a unique chess puzzle that is available for anyone to solve. And if you do manage to do so, then the Clay Mathematics Institute will be more than happy to hand over a million dollars to the first person to successfully solve it. The puzzle holds the key to unlock many other impossible problems which include breaking complex cryptography ciphers. Researchers estimate that this particular problem could take thousands of years before a solution is reached upon. The problem isn’t anything new but a scaled up version of the Queens Puzzle.
The Queens Puzzle
Originally devised in the year 1848, the Queens Puzzle problem requires the player to place 8 Queen chess pieces on a standard chess board in such a manner that no two queens could ever attack each other. The solution for the Queens Puzzle on a small scale is very simple. By placing just one queen in each row without two queens being in the same column and then you need to ensure that no two queens are in the same diagonal. In 1850, the first set of solutions for the puzzle was published and the puzzle was scaled to become the n Queens Problem.
The standard eight queens puzzle has been solved by humans and machines alike. It has 92 distinct solutions but if you discount solutions which are reflections or are symmetrical, then the number of solutions comes down to 12. These 12 solutions are termed the fundamental solutions for the 8 Queens Problem.
The 8 Queens Puzzle and its scaled up version i.e. the “n Queens Problem” has been widely studied in the computing universe for quite some time. Numerous algorithms are used to solve the puzzle and almost all involve backtracking in some form of the other. Backtracking is simply the approach of placing queens on the table till a conflict situation is arrived upon, and then the algorithm backtracks to the state prior to conflict to perform a different approach.
Scaling up – The n Queens Problem
The n Queens Problem states that you need to place ‘n’ number of Queens on an ‘n’x’n’ board. When n=1, the solution is simply a single queen placed on the only cell in an 1×1 chess board. However, when n=2 or n=3, there is no solution at all since two Queens will always fall along the same row, column or diagonal. When n=4, the number of solutions are 2, and with n=5 the number of solutions become 10.
As of now, the number of solutions for the n Queens Problem have only been enumerated up to n=27. And the number of solutions for that is 234,907,967,154,122,528. These include solutions which are symmetric and rotations. Finding all the solutions for higher order problems is difficult though finding just one solution is not. And that’s where the prize money comes into the picture.
Why the $1 Million prize?
There exist methods to find solutions for the n Queens Problem, however, finding every single solution isn’t as easy task. Currently there are no computers which can solve the problem where n=1000. There are shortcuts that one can take to avoid a purely brute force approach via backtracking but even those that are currently known become very intensive as the problem scales up.
Professor Ian Gent, of the University of St Andrews said, “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily. This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe.”
Backtracking involves figuring out whether each and every possible approach is feasible or not before “back tracking” to a previous state. Since this becomes a brute force approach, the time and computational resources involved are immense. Hence, if a new method is devised that allows for a quicker solution to the n Queens Problem, the same can then be applied across a myriad number of situations.
The paper that elaborates the complexity of the n Queens Problem can be found here.