N Queen Problem using Branch And Bound | C ++ 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 program to test above function
#include <stdio.h> NEW_LINE #include <string.h> NEW_LINE #define N  8 NEW_LINE void printSolution ( int board [ N ] [ N ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) printf ( " % 2d ▁ " , board [ i ] [ j ] ) ; printf ( " STRNEWLINE " ) ; } } bool isSafe ( int row , int col , int slashCode [ N ] [ N ] , int backslashCode [ N ] [ N ] , bool rowLookup [ ] , bool slashCodeLookup [ ] , bool backslashCodeLookup [ ] ) { if ( slashCodeLookup [ slashCode [ row ] [ col ] ] backslashCodeLookup [ backslashCode [ row ] [ col ] ] rowLookup [ row ] ) return false ; return true ; } bool solveNQueensUtil ( int board [ N ] [ N ] , int col , int slashCode [ N ] [ N ] , int backslashCode [ N ] [ N ] , bool rowLookup [ N ] , bool slashCodeLookup [ ] , bool backslashCodeLookup [ ] ) { 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 ; } bool solveNQueens ( ) { int board [ N ] [ N ] ; memset ( board , 0 , sizeof board ) ; int slashCode [ N ] [ N ] ; int backslashCode [ N ] [ N ] ; bool rowLookup [ N ] = { false } ; bool slashCodeLookup [ 2 * N - 1 ] = { false } ; bool backslashCodeLookup [ 2 * N - 1 ] = { false } ; 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 ) { printf ( " Solution ▁ does ▁ not ▁ exist " ) ; return false ; } printSolution ( board ) ; return true ; } int main ( ) { solveNQueens ( ) ; return 0 ; }