N queens problem

Question

I was requested to solve this task few days ago. And that confuse me a lot. It requires you to solve n queens problem and 4≤n≤1000. It is known we cannot use brute force, since the task requires at max 4 secs running time. I can't figure out how else I can do it. Can anyone give me some hints?

Answer 1

If you need just one solution, there are well-known algorithms.
https://en.m.wikipedia.org/wiki/Eight_queens_puzzle#Existence_of_solutions

http://penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf

Answer 2

https://code.sololearn.com/cH7a1P4e7Pb7/?ref=app
https://code.sololearn.com/cPF0SN57La7C/?ref=app

n = 1000 is a lot though 😓

Answer 3

You are going to need a programming language with good runtime so go with C++

Answer 4

Kishalaya Saha much thanks ❤️

Answer 5

Anna So your code is generating different queens on random position until whole plate is filled. Am I correct? If so, I don't think 4s is enough for the calculation.

Answer 6

Anna Is there any way to efficiently calculate? Something worth mentioning, I've found ALMOST every situation can be satisfied by starting from {1,2} ( {x - 1 to n ,y - 1 to n} )
Then jump 1 for x-coordinates, 2 for y. When the y index exceeds n, go the process again.

But 32, 128 won't do. I've tried

Answer 7

You're welcome, William Tseng 😊