N = int(input())
matrix = [[0 for x in range(N)] for y in range(N)]
def Print(matrix):
for row in matrix:
for elem in row:
print(elem, end=' ')
print()
def is_attacked(matrix,j,i,N):
for a in range(N):
for b in range(N):
if matrix[a][b]:
if j == a or i-j == b-a or b == i or i+j == b+a:
return(True)
return(False)
def alg(matrix,N,number_of_queens):
if number_of_queens == 0:
return(True)
for a in range(N):
for b in range(N):
if is_attacked(matrix,a,b,N):
continue
matrix[a][b] = 1
if alg(matrix,N,number_of_queens-1):
return(True)
else:
matrix[a][b] = 0
return(False)
if alg(matrix,N,N):
print("YES")
Print(matrix)
else:
print("NO")
This is the solution to the Eight queen chess problem on Hackerearth the problem is that i get time exceeded on my last input but i implemented the algorithm correctly and i revised the code maybe it is because python is slower from other languages.what takes time in my code?.Hackerearth link:https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/
Have you considered using a profiler?
$ echo "8" | python3 eightqueens.py
YES
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
1686133 function calls (1660190 primitive calls) in 6.467 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 6.467 6.467 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 codecs.py:318(decode)
1 0.000 0.000 0.000 0.000 eightqueens.py:1(Print)
25944/1 1.180 0.000 6.467 6.467 eightqueens.py:13(alg)
1 0.000 0.000 6.467 6.467 eightqueens.py:27(blaha)
8 0.000 0.000 0.000 0.000 eightqueens.py:29(<listcomp>)
1660100 5.286 0.000 5.286 0.000 eightqueens.py:6(is_attacked)
1 0.000 0.000 0.000 0.000 {built-in method _codecs.utf_8_decode}
1 0.000 0.000 6.467 6.467 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.input}
73 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Based on this, you can see that your is_attached() function is the most called function consuming by far most of the execution time. This is where you most likely want to focus your efforts if you want your code to run faster.
I modified your code slightly to get the result you see above. The code I used follows.
def Print(matrix):
for row in matrix:
for elem in row:
print(elem, end=' ')
print()
def is_attacked(matrix,j,i,N):
for a in range(N):
for b in range(N):
if matrix[a][b]:
if j == a or i-j == b-a or b == i or i+j == b+a:
return(True)
return(False)
def alg(matrix,N,number_of_queens):
if number_of_queens == 0:
return(True)
for a in range(N):
for b in range(N):
if is_attacked(matrix,a,b,N):
continue
matrix[a][b] = 1
if alg(matrix,N,number_of_queens-1):
return(True)
else:
matrix[a][b] = 0
return(False)
def blaha():
N = int(input())
matrix = [[0 for x in range(N)] for y in range(N)]
if alg(matrix,N,N):
print("YES")
Print(matrix)
else:
print("NO")
import cProfile
import re
cProfile.run('blaha()')
As you can see, I've just packaged the start of your code a bit differently in order to run the profiler.
From what I can see of your implementation I'd say you have a far too crude implementation in is_attacked(). You should really consider if it's really meaningful to always go through the entire board even if you have only put a few queens on the board. Spoiler: The answer is, of course, no.
Finding ways to terminate early is a common way to optimize algorithms and profiling is a quite useful keyhole to peek into to get some suggestions on where to focus.
On my modest computer, your algorithm found a solution for input "8" in just under four seconds, without the profiler. What input is the requirement and what time limit goes with it if I may ask?