9-2-17

Win $1 million By Creating a Computer Code to Solve This Simple Puzzle

Source Paranoid Times

Eight queens puzzle: $1m prize for anyone who can solve ‘simple’ chess puzzle

The gauntlet is thrown down to crack the eight queens puzzle – only one of the Millenium Prize Problems has ever been solved.

Researchers at the University of St Andrews are challenging people to claim $1m (£770,000) by finding the solution to a “simple” chess puzzle.

Computer programmers would be able to pocket the cash, which is offered by the Clay Mathematics Institute in America, if they found an efficient solution to the famous eight queens puzzle.

The puzzle requires a player to place eight chess queens on an 8×8 chessboard so that no two queens are threatening each other.

For an 8×8 chessboard, the solution requires that the queens don’t share the same row, column, or diagonal – the directions in which chess queens can move.

Considered as a mathematical problem, computer scientists have calculated there are 4,426,165,368 possible arrangements of the queens but of these arrangements, only 92 are acceptable solutions.

Originally devised in 1850, the 8×8 puzzle has been solved by humans – but once the size of the chess board increases enough, computer programmes have found it impossible to solve.

A paper published in the Journal of Artificial Intelligence Research concludes that the team led by Professor Ian Gent at the University of St Andrews noted a solution would provide enormous benefits to the world.

Professsor Gent said: “If you could write a computer programme 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.”

The underlying problem is one of the most major unsolved problems in computer science and mathematics.

Known as P versus NP, it is one of the seven Millennium Prize Problems which carry the million dollar reward for their first correct solution.

The P versus NP problem essentially asks whether, if it is easy to verify that the solution to a problem is correct, is it also easy to solve the problem too?

It is ultimately a problem about problems.

If there is a simple way to confirm that, for instance 967 multiplied by 839 equals 811,313, shouldn’t it therefore be equally easy to prove that 967 and 839 are the prime factors of 811,313?

Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a programme that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”

Only one Millennium Prize Problem has been solved since they were established in 2000.

Grigori Perelman turned down both the prize money and the Fields Medal, often called the Nobel Prize of Mathematics, for his work.

Mr Perelman said: “I’m not interested in money or fame; I don’t want to be on display like an animal in a zoo.”

Source sky news