# Solve N Queen Problem in O(n) space in Python

In this tutorial, we will learn about how to solve the N Queen problem in O(n) space using Python language.
N Queen Problem: This problem is just like a puzzle. In the NxN chessboard, N queens have placed in such a manner no two queens in the same row and same column also not in the same diagonal. This arrangement is the solution to the N Queen problem.

## N Queen Problem’s approach

Algorithm to check the place:

• Make a method to check the queen is placed in the ith row and jth column then return True. Otherwise, it returns False.
• Using for loop(k=1 to i-1) to check that two queens in the same column or same diagonal or not.
• If A[k]==j or Abs(A[k] – j) = Abs(k – i) then return False otherwise return True.
• A[] is the global array whose first (i-1) elements have been set.
• Abs() returns absolute value.

Algorithm for NQueens:

• Using the backtracking approach, this method prints every possible place for N Queens on the chessboard of NxN.
• Using this psedocode
• Method: N-Queens(i, N):
for k=1 to N:
if placement( i, j) then:
A[i] = j;
if i == N:
print A[1:N]
else
N-Queens(i+1, N)

implementation of the procedure:

class solution:
def __init__(self):
self.MAX = 100    # size of array
self.A = [0]*self.MAX

def placement(self,i,j):    # to check if queen can be placed
for k in range(1,i):
if (self.A[k] == j) or abs(self.A[k] - j) == abs(k - i):
return False
return True

def printplacedqueen(self,N):  # method for print the placed Queen
print('Arrangment--->')
print()

for i in range(1,N+1):
for j in range(1,N+1):
if self.A[i] != j:
print('\t_',end =' ')
else:
print('\tQ',end =' ')
print()
print()

def N_Queens(self,i,j):
for k in range(1,N+1):
if self.placement(i,k):
self.A[i] = k
if i == N:
self.printplacedqueen(N)
else:
self.N_Queens(i+1,N)

N = 4
obj = solution()
obj.N_Queens(1,N)

OUTPUT:

Arrangment--->

_ 	Q 	_ 	_

_ 	_ 	_ 	Q

Q 	_ 	_ 	_

_ 	_ 	Q 	_

Arrangment--->

_ 	_ 	Q 	_

Q 	_ 	_ 	_

_ 	_ 	_ 	Q

_ 	Q 	_ 	_

Thanks for visiting codespeedy. I hope it helps you.