N-Queens Problem | Design And Analysis of Algorithms | Backtracking | Python
Code:
def check(dp,row,col,n):
for i in range(row,-1,-1):
if dp[i-1][col]=='Q':
return False
for j in range(col,-1,-1):
if dp[row][j-1]=='Q':
return False
for i,j in zip(range(row,-1,-1),range(col,-1,-1)):
if dp[i][j]=='Q':
return False
for i,j in zip(range(row,n),range(col,-1,-1)):
if dp[i][j]=='Q':
return False
return True
def nqueens(dp,row,n):
if row==n:
return True
for col in range(0,n):
if check(dp,row,col,n):
dp[row][col] = 'Q'
if nqueens(dp,row+1,n):
return True
dp[row][col] = 0
if _name_ == '__main__':
n = 4
dp = [[0 for _ in range(0,n)]for _ in range(n)]
if nqueens(dp,0,n):
for i in range(0,n):
for j in range(0,n):
print(dp[i][j],end=' ')
print("\n")
#python #coding #programming #coder #backtracking #recursion #algorithm #nqueens #nqueensproblem #codingforall #cs #it #computerscience #btech