N Queen Problem using Branch And Bound | Java program to solve N Queen Problem using Branch and Bound ; A utility function to print 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 * and Bound . It mainly uses solveNQueensUtil ( ) 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 . ; 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 code
import java . io . * ; import java . util . Arrays ; class GFG { static int N = 8 ; static void printSolution ( int board [ ] [ ] ) { int N = board . length ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) System . out . printf ( " % 2d ▁ " , board [ i ] [ j ] ) ; System . out . printf ( "NEW_LINE"); } } static boolean isSafe ( int row , int col , int slashCode [ ] [ ] , int backslashCode [ ] [ ] , boolean rowLookup [ ] , boolean slashCodeLookup [ ] , boolean backslashCodeLookup [ ] ) { if ( slashCodeLookup [ slashCode [ row ] [ col ] ] backslashCodeLookup [ backslashCode [ row ] [ col ] ] rowLookup [ row ] ) return false ; return true ; } static boolean solveNQueensUtil ( int board [ ] [ ] , int col , int slashCode [ ] [ ] , int backslashCode [ ] [ ] , boolean rowLookup [ ] , boolean slashCodeLookup [ ] , boolean backslashCodeLookup [ ] ) { int N = board . length ; if ( col >= N ) return true ; for ( int i = 0 ; i < N ; i ++ ) { if ( isSafe ( i , col , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) ) { board [ i ] [ col ] = 1 ; rowLookup [ i ] = true ; slashCodeLookup [ slashCode [ i ] [ col ] ] = true ; backslashCodeLookup [ backslashCode [ i ] [ col ] ] = true ; if ( solveNQueensUtil ( board , col + 1 , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) ) return true ; board [ i ] [ col ] = 0 ; rowLookup [ i ] = false ; slashCodeLookup [ slashCode [ i ] [ col ] ] = false ; backslashCodeLookup [ backslashCode [ i ] [ col ] ] = false ; } } return false ; } static boolean solveNQueens ( ) { int board [ ] [ ] = new int [ N ] [ N ] ; int slashCode [ ] [ ] = new int [ N ] [ N ] ; int backslashCode [ ] [ ] = new int [ N ] [ N ] ; boolean [ ] rowLookup = new boolean [ N ] ; boolean slashCodeLookup [ ] = new boolean [ 2 * N - 1 ] ; boolean backslashCodeLookup [ ] = new boolean [ 2 * N - 1 ] ; for ( int r = 0 ; r < N ; r ++ ) for ( int c = 0 ; c < N ; c ++ ) { slashCode [ r ] = r + c ; backslashCode [ r ] = r - c + 7 ; } if ( solveNQueensUtil ( board , 0 , slashCode , backslashCode , rowLookup , slashCodeLookup , backslashCodeLookup ) == false ) { System . out . printf ( " Solution ▁ does ▁ not ▁ exist " ) ; return false ; } printSolution ( board ) ; return true ; } public static void main ( String [ ] args ) { solveNQueens ( ) ; } }