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.
Leave a Reply