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.