N Queens Completion Is NP Complete
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 Notes On Structured Programming. It was used as an example of how recursion-based backtracking can be used to solve a problem far more easily than any other approach. I can't say I've thought about it much since, apart from using it as an advanced example of recursion.

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.

Q81

A symmetric solution

 

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.

"We have presented generators for hard random instances of the Blocked n-Queens and Excluded Diagonals problems, shown that this hardness persists across three solvers using very different technologies, and that the hardness is associated with a phase transition in solvability. A natural model for n-Queens Completion does not appear to generate consistently hard instances. We have also shown that care must be taken in generation methods to avoid flaws which can be found in extant benchmarks. Our experiments raise many interesting questions for future research. These include the asymptotic scaling of the transition in Blocked n-Queens and the Excluded Diagonals problems. An interesting open problem is to find a direct generator of hard random instances for n-Queens Completion which works by randomly placing queens on a chessboard without using reductions."

If you have never thought about it before. the idea that different generators of examples might create easy or hard examples is intriguing.

More Information

Complexity of n-Queens Completion

Related Articles

New 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

NP-Complete - Why So Hard?

NP Complete

Classic Nintendo Games Are NP Hard

Physics Is 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, FacebookGoogle+ or Linkedin.

 

Banner


SciPy1.0 Released
26/10/2017

SciPy, the widely used open source Python library used for scientific and technical computing, has reached the milestone of a Version 1.0 release. This maturity is completed by a governance model [ ... ]



Facebook Open Sources RacerD For Android Race Detection
23/10/2017

It is a hardly discussed problem, but Android is a tough platform to use with concurrent programming. As a result most apps don't use it to its full potential. Facebook has now gifted you a tool that  [ ... ]


More News

 

 
 

 

blog comments powered by Disqus

 

 <ASIN:0122005503>

Last Updated ( Friday, 01 September 2017 )
 
 

   
Banner
Banner
RSS feed of news items only
I Programmer News
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.