Some people say yes, as the time complexity is N!, while some researchers claim that there are some polynomial time algorithms such as: http://dl.acm.org/citation.cfm?id=101343
Same thing applies for the assignment problem, if it is NP hard then what about the Hungarian method which runs in O(n^3) time?
If both NP hard and there are some polynomial time algorithms to solve em then P=NP?
To find one solution it is linear time. There is a pattern for that.
For even number of N,
put the first queen at slot 2
put the second queen at slot 4.
....
put the n/2+1 th queen at slot 1
put the n/2+2 th queen at slot 3
...
=====
Similarly you can find one solution for odd n.
====
To find all the solution, it is not NP, it should be exponential. As the number of solutions is exponential. So it should not be in the NP set.
Yes it is NP Hard .. we developed ACO based solution to n-Queen problem ...
Referring to our Paper title "Ant n-Queen Solver"
http://www.ceser.in/ceserp/index.php/ijai/article/view/1192
I think the confusion is in the interpretation of the word "solve". Those algorithms you mentioned "solve" an NP-Hard problem in the sense that they find a solution, but not necessarily the optimal. Of course their complexity is polynomial and perhaps they get near-optimal solutions or even the optimal ones for some instances, but still they are not "exact polynomial algorithms". If there is an "exact polynomial algorithm" for an NP-Hard problem then P=NP, but such algorithm has not been found yet.
Jesus has a good point. For some NP-complete problems, even getting an approximate answer (say, within 5% of optimal) is also NP-complete. For others, there are simple algorithms to get approximate solutions, and only getting the exact best solution is hard. For example, for the Traveling Salesman problem, there is an efficient method based on minimum spanning tree that is guaranteed to give a path no longer than twice the minimum length.
You also need to be careful what you mean by "the N-queens problem". For example, the game of Hex (viewed as the set of all possible Hex positions) is PSPACE-complete, but it's not at all clear that playing Hex starting from an empty board is nearly that hard. There is a trivial strategy-stealing proof that the empty board is a first-player win, but there is NO easy way of finding the status of an arbitrary Hex position.
In your case: do you mean, the problem of placing N queens on an empty NxN board, or the problem (given M < N already-placed queens) of determining whether there is a way to extend that to an N-queens solution by adding more queens? Those are different problems and may have different complexity.
To find one solution it is linear time. There is a pattern for that.
For even number of N,
put the first queen at slot 2
put the second queen at slot 4.
....
put the n/2+1 th queen at slot 1
put the n/2+2 th queen at slot 3
...
=====
Similarly you can find one solution for odd n.
====
To find all the solution, it is not NP, it should be exponential. As the number of solutions is exponential. So it should not be in the NP set.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms