N Queen Problem using Branch And Bound | Python3 program to solve N Queen Problem using Branch or Bound ; A utility function to pri nt solution ; A Optimized function to check if a queen can be placed on board [ row ] [ col ] ; 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 ; Check if queen can be placed on board [ i ] [ col ] ; Place this queen in board [ i ] [ col ] ; recur to place rest of the queens ; Remove queen from board [ i ] [ col ] ; If queen can not be place in any row in this colum col then return False ; This function solves the N Queen problem using Branch or Bound . It mainly uses solveNQueensUtil ( ) to solve the problem . It returns False if queens cannot be placed , otherwise return True or 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 . ; helper matrices ; arrays to tell us which rows are occupied ; keep two arrays to tell us which diagonals are occupied ; initialize helper matrices ; solution found ; Driver Cde
N = 8 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 isSafe ( row , col , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) : NEW_LINE INDENT if ( slashCodeLookup [ slashCode [ row ] [ col ] ] or backslashCodeLookup [ backslashCode [ row ] [ col ] ] or rowLookup [ row ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def solveNQueensUtil ( board , col , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) : NEW_LINE INDENT if ( col >= N ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( isSafe ( i , col , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) ) : NEW_LINE INDENT board [ i ] [ col ] = 1 NEW_LINE rowLookup [ i ] = True NEW_LINE slashCodeLookup [ slashCode [ i ] [ col ] ] = True NEW_LINE backslashCodeLookup [ backslashCode [ i ] [ col ] ] = True NEW_LINE if ( solveNQueensUtil ( board , col + 1 , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT board [ i ] [ col ] = 0 NEW_LINE rowLookup [ i ] = False NEW_LINE slashCodeLookup [ slashCode [ i ] [ col ] ] = False NEW_LINE backslashCodeLookup [ backslashCode [ i ] [ col ] ] = False NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def solveNQueens ( ) : NEW_LINE INDENT board = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE slashCode = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE backslashCode = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE rowLookup = [ False ] * N NEW_LINE x = 2 * N - 1 NEW_LINE slashCodeLookup = [ False ] * x NEW_LINE backslashCodeLookup = [ False ] * x NEW_LINE for rr in range ( N ) : NEW_LINE INDENT for cc in range ( N ) : NEW_LINE INDENT slashCode [ rr ] [ cc ] = rr + cc NEW_LINE backslashCode [ rr ] [ cc ] = rr - cc + 7 NEW_LINE DEDENT DEDENT if ( solveNQueensUtil ( board , 0 , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) == False ) : NEW_LINE INDENT print ( " Solution ▁ does ▁ not ▁ exist " ) NEW_LINE return False NEW_LINE DEDENT printSolution ( board ) NEW_LINE return True NEW_LINE DEDENT solveNQueens ( ) NEW_LINE