What makes this code slow?

Question

I tried a backtracking solution for n-queens problem. I noticed that it works only for n < 7.

Did I something wrong or is it just not good how I check if a queen is safe or not?
https://code.sololearn.com/cO6R3CIo0PK2/?ref=app

This one is a copy from Vitaly's code and it seems to be faster (works for n = 7).
https://code.sololearn.com/c1LTb48mAIq1/?ref=app

Answer 1

I have made backtracking codes long ago for this problem, and it worked with n=11 to find all solutions and n=21 to find the first solution.
I was using only vanilla lists, not numpy.

https://code.sololearn.com/cw485MTC064u/?ref=app
https://code.sololearn.com/cf32yLv8KVjz/?ref=app

The more scientific approach to figure out what is slowing down your code, would be to use a profiler tool, but I haven't tried any of those.
https://stackify.com/how-to-use-JUMP_LINK__&&__python__&&__JUMP_LINK-profilers-learn-the-basics/

Answer 2

I'm pretty sure I read somewhere that "if" slows down every code. You have a lot more ifs in your code than Vitaly's.

I'll see if I can find a link about it for you.
https://stackoverflow.com/questions/12240472/why-does-adding-an-if-statement-inside-a-this-method-slow-it-down-so-drastically

Answer 3

Denise Roßberg
There is a YouTube video with an alternative solution to the N-Queens Problem using itertools permutations and set intersection.

I copied it here, with cosmetic upgrade.

extra link:
http://www.durangobill.com/N_Queens.html

https://code.sololearn.com/ck3407WNXj8z/?ref=app

Answer 4

Tibor Santa

Thanks for your answer!
Do you mean something like this? https://docs.python.org/3/library/profile.html

Answer 5

Denise Roßberg yes I think that is one approach, probably there are also other tools, but if it's already in the standard library then this one might even work on SL :)

Answer 6

Ausgrindtube

Interesting. I will see what happens when I reduce some if statements.

Answer 7

Ausgrindtube

It seems not really to change something.

https://code.sololearn.com/cK64bz27s8Du/?ref=app

Answer 8

I also looked (and counted) the ifs, you don't have so many more at all. I think it's 6 vs 5! Perhaps it's the difference in position?

I've found this https://www.freecodecamp.org/news/if-you-have-slow-loops-in-JUMP_LINK__&&__python__&&__JUMP_LINK-you-can-fix-it-until-you-cant-3a39e03b6f35/
It's not so easy to read, but seems to go through many options for things that slow down a code.