N Queen Problem | Backtracking | Java 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
import java . util . * ; class GFG { static int N = 4 ; static int [ ] ld = new int [ 30 ] ; static int [ ] rd = new int [ 30 ] ; static int [ ] cl = new int [ 30 ] ; static void printSolution ( int board [ ] [ ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) System . out . printf ( " ▁ % d ▁ " , board [ i ] [ j ] ) ; System . out . printf ( "NEW_LINE"); } } static boolean solveNQUtil ( int board [ ] [ ] , int col ) { if ( col >= N ) return true ; for ( int i = 0 ; i < N ; i ++ ) { if ( ( ld [ i - col + N - 1 ] != 1 && rd [ i + col ] != 1 ) && cl [ i ] != 1 ) { board [ i ] [ col ] = 1 ; ld [ i - col + N - 1 ] = rd [ i + col ] = cl [ i ] = 1 ; if ( solveNQUtil ( board , col + 1 ) ) return true ; ld [ i - col + N - 1 ] = rd [ i + col ] = cl [ i ] = 0 ; } } return false ; } static boolean solveNQ ( ) { int board [ ] [ ] = { { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } } ; if ( solveNQUtil ( board , 0 ) == false ) { System . out . printf ( " Solution ▁ does ▁ not ▁ exist " ) ; return false ; } printSolution ( board ) ; return true ; } public static void main ( String [ ] args ) { solveNQ ( ) ; } }