N Queens Completion Is NP Complete |

Written by Mike James | |||

Thursday, 31 August 2017 | |||

The problem of putting eight queens on the chess board so as no queen attacks another is a solved problem, as is placing n queens on an nxn board. However if you place some queens on the board and ask for a completion then the problem is NP complete. The 8 queens problem is quite old and I met it first not as a chess player but as part of reading Dijkstra's If you have never tried the 8 queens problem give it a go - use a chess board and 8 pawns as if they were queens. As you can imagine, it starts out difficult and gets worse as you add queens. This is the reason that another version of the problem, the n queens completion puzzle in which some of the queens have already been placed, is popular.
A new paper by Ian Gent, Peter Nightingale and Christopher Jefferson, all of the School of Computer Science at the University of St Andrews, is the result of a friend challenging Professor Gent to solve it on Facebook. In it, and it's 34 pages long so be warned, it is proved the n queens completion problem is NP Complete and #P Complete. As a reminder, NP is the set of problems that are hard to solve but for which it is easy to check a proposed solution. Clearly n queens completion is easy to check if I give you a solution, but experience suggests it is hard to find a solution. An NP Complete problem is one that if you can find a way to solve it quickly, i.e. in polynomial time, then you can solve all problems in polynomial time and you have proved P=NP, which would be a big deal because most of our cryptography depends on P≠NP, not to mention the one million dollar prize from the Clay Math Institute. The #P complexity class is the set of problems related to NP that simply asks how many solutions there are. In the n queens case the question is how many solution are there for any n and this is clearly just as hard is the NP problem itself. As for NP Complete, a #P Complete problem is one that if you can solve it in polynomial time then you can solve all problems in #P in polynomial time. Given the size of the space you have to search to find a solution, these results might not suprise you. However the number of solutions for n queens is known only to n=27 and the number of solutions is more than 2.34*10^17. The question is how hard are they to solve in practice. To answer this question three different solvers were implemented for three different variations on the basic problems. Normally NP Complete problems show a "phase transition" from solvable to unsolvable as n increases.
If you have never thought about it before. the idea that different generators of examples might create easy or hard examples is intriguing. ## More InformationComplexity of n-Queens Completion ## Related ArticlesNew Proof That P≠NP: Update - Probably Not Rubik's Cube Is Hard - NP Hard Column Subset Selection Is NP-complete Unshuffling A Square Is NP-Complete Classic Nintendo Games Are NP Hard
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info
<ASIN:0122005503> |
|||

Last Updated ( Friday, 01 September 2017 ) |