N Queen Problem | Backtracking | Python3 program to solve N Queen Problem using backtracking ; ld is an array where its indices indicate row - col + N - 1 ( N - 1 ) is for shifting the difference to store negative indices ; rd is an array where its indices indicate row + col and used to check whether a queen can be placed on right diagonal or not ; column array where its indices indicates column and used to check whether a queen can be placed in that row or not ; A utility function to print solution ; A recursive utility function to solve N Queen problem ; base case : If all queens are placed then return True ; Consider this column and try placing this queen in all rows one by one ; A check if a queen can be placed on board [ row ] [ col ] . We just need to check ld [ row - col + n - 1 ] and rd [ row + coln ] where ld and rd are for left and right diagonal respectively ; Place this queen in board [ i ] [ col ] ; recur to place rest of the queens ; board [ i ] [ col ] = 0 BACKTRACK ; If the queen cannot be placed in any row in this colum col then return False ; This function solves the N Queen problem using Backtracking . It mainly uses solveNQUtil ( ) to solve the problem . It returns False if queens cannot be placed , otherwise , return True and prints placement of queens in the form of 1 s . Please note that there may be more than one solutions , this function prints one of the feasible solutions . ; Driver Code
N = 4 NEW_LINE ld = [ 0 ] * 30 NEW_LINE rd = [ 0 ] * 30 NEW_LINE cl = [ 0 ] * 30 NEW_LINE def printSolution ( board ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT print ( board [ i ] [ j ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT def solveNQUtil ( board , col ) : NEW_LINE INDENT if ( col >= N ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( ( ld [ i - col + N - 1 ] != 1 and rd [ i + col ] != 1 ) and cl [ i ] != 1 ) : NEW_LINE INDENT board [ i ] [ col ] = 1 NEW_LINE ld [ i - col + N - 1 ] = rd [ i + col ] = cl [ i ] = 1 NEW_LINE if ( solveNQUtil ( board , col + 1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT ld [ i - col + N - 1 ] = rd [ i + col ] = cl [ i ] = 0 NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def solveNQ ( ) : NEW_LINE INDENT board = [ [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] ] NEW_LINE if ( solveNQUtil ( board , 0 ) == False ) : NEW_LINE INDENT printf ( " Solution ▁ does ▁ not ▁ exist " ) NEW_LINE return False NEW_LINE DEDENT printSolution ( board ) NEW_LINE return True NEW_LINE DEDENT solveNQ ( ) NEW_LINE