N Queen in O ( n ) space | Python code to for n Queen placement ; Helper Function to check if queen can be placed ; Function to display placed queen ; Function to check queens placement ; Driver Code
class GfG : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . MAX = 10 NEW_LINE self . arr = [ 0 ] * self . MAX NEW_LINE self . no = 0 NEW_LINE DEDENT def breakLine ( self ) : NEW_LINE INDENT print ( " - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) NEW_LINE DEDENT def canPlace ( self , k , i ) : NEW_LINE INDENT for j in range ( 1 , k ) : NEW_LINE INDENT if ( self . arr [ j ] == i or ( abs ( self . arr [ j ] - i ) == abs ( j - k ) ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def display ( self , n ) : NEW_LINE INDENT self . breakLine ( ) NEW_LINE self . no += 1 NEW_LINE print ( " Arrangement ▁ No . " , self . no , end = " ▁ " ) NEW_LINE self . breakLine ( ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if self . arr [ i ] != j : NEW_LINE INDENT print ( " TABSYMBOL _ " , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " TABSYMBOL Q " , end = " ▁ " ) NEW_LINE DEDENT DEDENT print ( ) NEW_LINE DEDENT self . breakLine ( ) NEW_LINE DEDENT def nQueens ( self , k , n ) : NEW_LINE INDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if self . canPlace ( k , i ) : NEW_LINE INDENT self . arr [ k ] = i NEW_LINE if k == n : NEW_LINE INDENT self . display ( n ) NEW_LINE DEDENT else : NEW_LINE INDENT self . nQueens ( k + 1 , n ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE obj = GfG ( ) NEW_LINE obj . nQueens ( 1 , n ) NEW_LINE DEDENT