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


Top 10 From Around the Web: More PHP Development Resources
01/09/2017

PHP is focus for this roundup of external blog posts. While PHP may not be the most trendy web development language, it is what is behind the scenes of many of the websites we use daily. Here we prese [ ... ]



Safari Will Remove AMP Links
25/08/2017

Browsers are supposed to simply read the standard HTML and render it faithfully - but of course we know they don't. Now Apple's Safari is starting to rewrite URLs from Google's AMP cache to point to t [ ... ]


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.