Toughest math problems much harder than chess

The above picture shows a chessboard with two queens placed on it. As the queens do not share the same row, column or diagonal of the chessboard they are not attacking each other. Can you place another six queens on the board so that none of the eight queens are attacking each other? And if it’s possible, how many ways are there to do it?

This illustrated puzzle using a typical chessboard, an example of what is called the 8-queens completion problem, is from 1850. Yet only now, in a paper written by Chris Jefferson, Peter Nightingale and me published in the Journal of Artificial Intelligence Research, have we confirmed the depth of complexity hidden within the puzzle when scaled up to allow for boards of any size, with any number of queens pre-placed in any arrangement on the board – a much harder version of the puzzle known as n-queens completion.

Unfortunately, due to misunderstandings when our paper was reported by the media (here for example, or here with correction) many people now think I am going to pay them US$1m. I am sorry to disappoint them, and hope here to put the record straight.

The n-queens completion puzzle is a form of mathematical problem common in computer science and described as “NP-complete”. These are interesting problems because if an efficient solution can be found for one NP-complete problem, it can be used to solve all NP-complete problems.

Some of these puzzles may seem unimportant – identifying the largest number of Facebook friends that don’t know each other, for example. But a fast and efficient solution to this problem could also be used to solve other problems with a more practical purpose – for example, calculating the password used to encrypt data sent between a web browser and a bank. While it may seem odd that the placement of queens on a chessboard can in some way be translated to password encryption, that is indeed the case. That is the nature of all NP-complete problems.

Completion, check

Thousands of problems have been proved to be NP-complete. What I like about n-queens completion is that it is one of the simplest NP-complete problems to explain, especially to people who know the rules of chess. It is also a simple variant of one of the most widely studied problems in artificial intelligence: n-queens, which is the same puzzle but starting with an empty board rather than one with pre-placed queens. Following our paper, we now understand that the reason why the n-queens completion problem is so much harder than the version with an empty board is that it is an example of an NP-complete problem.

Nobody knows, even very roughly, how hard NP-complete problems are. They could be as easy as sorting a list of names into alphabetical order, or they could be exponentially harder. Finding out which they are is called the P vs NP problem, and it is one of the great unsolved mathematical problems – so much so that the Clay Mathematics Institute (not me) is offering a prize of US$1m for the solution of P vs NP.

Checkmate

Since our paper shows that the n-queens completion problem is NP-complete, anyone able to show whether it’s an easy or difficult problem could win a million dollars. This seemed an obvious hook to publicise our paper, and while we were delighted to take part – with Peter and I posing with giant chess pieces – we only wish that the reporting hadn’t given people the impression they could win the money for solving the n-queens problem, rather than the P vs NP problem that is far harder … and potentially unsolveable.

It’s possible the reason people misunderstood what was required to win the Clay Institute’s prize is how many layers removed the prize requirements is from solving chess puzzles.

1. First, they needed to be tackling the right problem, since n-queens is easy and n-queens completion is hard.
2. Second, it is not enough to solve instances on a standard 8-by-8 chessboard. For example, we already know that the 8-queens completion problem from 1850 has two possible answers. People have to solve the problem for any sized chessboard.
3. The third layer is to solve the puzzle not just for a particular layout of queens, but for any possible layout of any possible number of queens on a board of any possible size. Even finding algorithms for this level of n-queens completion is not enough.
4. The fourth layer is to not just solve the puzzle, but to mathematically prove the properties of the algorithms that have given you the answer. This is where the prize money is: to solve the wider P vs NP question, one must either mathematically prove that an algorithm exists that can solve n-queens completion efficiently (technically, in “polynomial time”) or alternatively to mathematically prove that this is impossible. And, in either case, to have published this work in journals for the world’s mathematicians to pore over for two years.

It’s possible that we hadn’t made clear the sheer complexity of the task required to win the prize money. It might be said that we failed to explain these layers very well. If I may help those still aiming for the prize, however, I would advise the following:

1. Get a PhD in computational complexity
2. Be brilliant
3. Be very, very, lucky

Ian Gent, Professor of Computer Science, University of St Andrews

This article was originally published on The Conversation and is republished here with permission. Read the original article.