You know about 1000-queens challenge?

Question

Sorry for my english, i make a code, this code print the solution for case 700 queens in one second or less, but my teacher tell me: "not is the solution for the p-np problem" or something.

Answer 1

Are you sure you did the solution right?
You basically need to place n queens on a board of 1000 by 1000 without any queen attacking the other one.

In case someone is not familiar with it check the below link for some info
http://indianexpress.com/article/technology/science/researchers-announce-1-mn-prize-to-build-computer-programme-to-solve-queens-puzzle-4827770/

A discussion about the same in the below post.
https://www.sololearn.com/discuss/685610/?ref=app

Answer 2

I'm not sure what you're asking. 3 lines:
*. What I must do.
*. What I did.
*. Why it's "wrong"
...would help.

Answer 3

What is wrong?, i catch the 1000 queens, but the one million need what?

Answer 4

The idea is that the program you came up with must be able to solve the problem in the same amount of time it takes to verify that the solution is correct.

The 1000 queens problem is a classic example of an NP-complete problem. What that means is that it's easy for a computer to tell if the placement of the queens is correct, but actually figuring out the correct placement of the queens is much harder.

For this problem, verification is easy: all you have to do is check if any queens can be captured. Thing is, finding a solution is a lot more complex than that, since the number of possible solutions to the problem becomes exponentially larger when more queens are added. Your computer may be able to find a solution for 1000 queens within a second, but it takes only a few microseconds for the computer to determine whether or not the solution works.

Sorry if that's complicated. This is one of the Millennium Prize Problems, and for good reason.

Answer 5

DaemonThread, well said! If I might add, finding *a* solution to the n-queens problem is also fairly easy. There are well-known algorithms that would do it in linear time.

If I'm not mistaken, it's about finding a solution to the n-queens COMPLETION problem, which starts with some queens already placed on the board.

Now finding a polynomial-time algorithm to *that* would be something!

Answer 6

I solv the 1000 queens, but not is the necessary for one million, my question is why not?, Yes i solv this problem

Answer 7

well i need search the all solutions for the problem?

Answer 8

According to Wikipedia, placing each queen in its own row and column and then using heuristic analysis to find the worst conflict and move the piece accordingly is the best approach. There's a link to the article in the other thread.