N Queen Problem using Backtracking
The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.
Below is the recursive tree of the above approach:
Follow the steps mentioned below to implement the idea:
- Start in the leftmost column
- If all queens are placed return true
- Try all rows in the current column. Do the following for every row.
- If the queen can be placed safely in this row
- Then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
- If placing the queen in [row, column] leads to a solution then return true.
- If placing queen doesn’t lead to a solution then unmark this [row, column] then backtrack and try other rows.
- If all rows have been tried and valid solution is not found return false to trigger backtracking.
- If the queen can be placed safely in this row
For better visualisation of this backtracking approach, please refer 4 Queen problem.
Note: We can also solve this problem by placing queens in rows as well.
Below is the implementation of the above approach:
C++
// C++ program to solve N Queen Problem using backtracking #include <bits/stdc++.h> #define N 4 using namespace std; // A utility function to print solution void printSolution( int board[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) if (board[i][j]) cout << "Q " ; else cout<< ". " ; printf ( "\n" ); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when "col" queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe( int board[N][N], int row, int col) { int i, j; // Check this row on left side for (i = 0; i < col; i++) if (board[row][i]) return false ; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false ; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j]) return false ; return true ; } // A recursive utility function to solve N // Queen problem bool solveNQUtil( int board[N][N], int col) { // base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] if (isSafe(board, i, col)) { // Place this queen in board[i][col] board[i][col] = 1; // recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true ; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false ) { cout << "Solution does not exist" ; return false ; } printSolution(board); return true ; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to solve N Queen Problem using backtracking #define N 4 #include <stdbool.h> #include <stdio.h> // A utility function to print solution void printSolution( int board[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (board[i][j]) printf ( "Q " ); else printf ( ". " ); } printf ( "\n" ); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when "col" queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe( int board[N][N], int row, int col) { int i, j; // Check this row on left side for (i = 0; i < col; i++) if (board[row][i]) return false ; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false ; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j]) return false ; return true ; } // A recursive utility function to solve N // Queen problem bool solveNQUtil( int board[N][N], int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] if (isSafe(board, i, col)) { // Place this queen in board[i][col] board[i][col] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true ; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false ) { printf ( "Solution does not exist" ); return false ; } printSolution(board); return true ; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to solve N Queen Problem using backtracking public class NQueenProblem { final int N = 4 ; // A utility function to print solution void printSolution( int board[][]) { for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { if (board[i][j] == 1 ) System.out.print( "Q " ); else System.out.print( ". " ); } System.out.println(); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when "col" queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens boolean isSafe( int board[][], int row, int col) { int i, j; // Check this row on left side for (i = 0 ; i < col; i++) if (board[row][i] == 1 ) return false ; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0 ; i--, j--) if (board[i][j] == 1 ) return false ; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j] == 1 ) return false ; return true ; } // A recursive utility function to solve N // Queen problem boolean solveNQUtil( int board[][], int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0 ; i < N; i++) { // Check if the queen can be placed on // board[i][col] if (isSafe(board, i, col)) { // Place this queen in board[i][col] board[i][col] = 1 ; // Recur to place rest of the queens if (solveNQUtil(board, col + 1 ) == true ) return true ; // If placing queen in board[i][col] // doesn't lead to a solution then // remove queen from board[i][col] board[i][col] = 0 ; // BACKTRACK } } // If the queen can not be placed in any row in // this column col, then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. 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.print( "Solution does not exist" ); return false ; } printSolution(board); return true ; } // Driver program to test above function public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // This code is contributed by Abhishek Shankhadhar |
Python3
# Python3 program to solve N Queen # Problem using backtracking global N N = 4 def printSolution(board): for i in range (N): for j in range (N): if board[i][j] = = 1 : print ( "Q" ,end = " " ) else : print ( "." ,end = " " ) print () # A utility function to check if a queen can # be placed on board[row][col]. Note that this # function is called when "col" queens are # already placed in columns from 0 to col -1. # So we need to check only left side for # attacking queens def isSafe(board, row, col): # Check this row on left side for i in range (col): if board[row][i] = = 1 : return False # Check upper diagonal on left side for i, j in zip ( range (row, - 1 , - 1 ), range (col, - 1 , - 1 )): if board[i][j] = = 1 : return False # Check lower diagonal on left side for i, j in zip ( range (row, N, 1 ), range (col, - 1 , - 1 )): if board[i][j] = = 1 : return False return True def solveNQUtil(board, col): # Base case: If all queens are placed # then return true if col > = N: return True # Consider this column and try placing # this queen in all rows one by one for i in range (N): if isSafe(board, i, col): # Place this queen in board[i][col] board[i][col] = 1 # Recur to place rest of the queens if solveNQUtil(board, col + 1 ) = = True : return True # If placing queen in board[i][col # doesn't lead to a solution, then # queen from board[i][col] board[i][col] = 0 # If the queen can not be placed in any row in # this column col then return false 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 # placement of queens in the form of 1s. # note that there may be more than one # solutions, this function prints one of the # feasible solutions. def solveNQ(): board = [[ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ]] if solveNQUtil(board, 0 ) = = False : print ( "Solution does not exist" ) return False printSolution(board) return True # Driver Code if __name__ = = '__main__' : solveNQ() # This code is contributed by Divyanshu Mehta |
C#
// C# program to solve N Queen Problem // using backtracking using System; class GFG { readonly int N = 4; // A utility function to print solution void printSolution( int [,]board) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (board[i, j] == 1) Console.Write( "Q " ); else Console.Write( ". " ); } Console.WriteLine(); } } // A utility function to check if a queen can // be placed on board[row,col]. Note that this // function is called when "col" queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens bool isSafe( int [,]board, int row, int col) { int i, j; // Check this row on left side for (i = 0; i < col; i++) if (board[row,i] == 1) return false ; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i,j] == 1) return false ; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i, j] == 1) return false ; return true ; } // A recursive utility function to solve N // Queen problem bool solveNQUtil( int [,]board, int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i,col] if (isSafe(board, i, col)) { // Place this queen in board[i,col] board[i, col] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1) == true ) return true ; // If placing queen in board[i,col] // doesn't lead to a solution then // remove queen from board[i,col] board[i, col] = 0; // BACKTRACK } } // If the queen can not be placed in any row in // this column col, then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. bool solveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == false ) { Console.Write( "Solution does not exist" ); return false ; } printSolution(board); return true ; } // Driver Code public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to solve N Queen // Problem using backtracking const N = 4 function printSolution(board) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (board[i][j] == 1) document.write( "Q " ) else document.write( ". " ) } document.write( "</br>" ) } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when "col" queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens function isSafe(board, row, col) { // Check this row on left side for (let i = 0; i < col; i++){ if (board[row][i] == 1) return false } // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j]) return false return true } function solveNQUtil(board, col){ // base case: If all queens are placed // then return true if (col >= N) return true // Consider this column and try placing // this queen in all rows one by one for (let i=0;i<N;i++){ if (isSafe(board, i, col)== true ){ // Place this queen in board[i][col] board[i][col] = 1 // recur to place rest of the queens if (solveNQUtil(board, col + 1) == true ) return true // If placing queen in board[i][col // doesn't lead to a solution, then // queen from board[i][col] board[i][col] = 0 } } // if the queen can not be placed in any row in // this column col then return false 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 // placement of queens in the form of 1s. // note that there may be more than one // solutions, this function prints one of the // feasible solutions. function solveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] if (solveNQUtil(board, 0) == false ){ document.write( "Solution does not exist" ) return false } printSolution(board) return true } // Driver Code solveNQ() // This code is contributed by shinjanpatra </script> |
. . Q . Q . . . . . . Q . Q . .
Time Complexity: O(N!)
Auxiliary Space: O(N2)
Further Optimization in is_safe() function:
The idea is not to check every element in the right and left diagonal, instead use the property of diagonals:
- The sum of i and j is constant and unique for each right diagonal, where i is the row of elements and j is the
column of elements.- The difference between i and j is constant and unique for each left diagonal, where i and j are row and column of element respectively.
Below is the implementation:
C++
// C++ program to solve N Queen Problem using backtracking #include <bits/stdc++.h> using namespace std; #define N 4 // ld is an array where its indices indicate row-col+N-1 // (N-1) is for shifting the difference to store negative // indices int ld[30] = { 0 }; // 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 int rd[30] = { 0 }; // Column array where its indices indicates column and // used to check whether a queen can be placed in that // row or not*/ int cl[30] = { 0 }; // A utility function to print solution void printSolution( int board[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << " " << (board[i][j]==1? "Q" : "." ) << " " ; cout << endl; } } // A recursive utility function to solve N // Queen problem bool solveNQUtil( int board[N][N], int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] // To 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 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Place this queen in board[i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true ; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false ) { cout << "Solution does not exist" ; return false ; } printSolution(board); return true ; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to solve N Queen Problem using backtracking import java.util.*; class GFG { static int N = 4 ; // ld is an array where its indices indicate row-col+N-1 // (N-1) is for shifting the difference to store // negative indices static int [] ld = new int [ 30 ]; // 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 static int [] rd = new int [ 30 ]; // Column array where its indices indicates column and // used to check whether a queen can be placed in that // row or not static int [] cl = new int [ 30 ]; // A utility function to print solution 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( "\n" ); } } // A recursive utility function to solve N // Queen problem static boolean solveNQUtil( int board[][], int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0 ; i < N; i++) { // Check if the queen can be placed on // board[i][col] // To 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 if ((ld[i - col + N - 1 ] != 1 && rd[i + col] != 1 ) && cl[i] != 1 ) { // Place this queen in board[i][col] board[i][col] = 1 ; ld[i - col + N - 1 ] = rd[i + col] = cl[i] = 1 ; // Recur to place rest of the queens if (solveNQUtil(board, col + 1 )) return true ; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0 ; // BACKTRACK ld[i - col + N - 1 ] = rd[i + col] = cl[i] = 0 ; } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. 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 ; } // Driver Code public static void main(String[] args) { solveNQ(); } } // This code is contributed by Princi Singh |
Python3
# Python3 program to solve N Queen Problem using # backtracking N = 4 # ld is an array where its indices indicate row-col+N-1 # (N-1) is for shifting the difference to store negative # indices ld = [ 0 ] * 30 # 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 rd = [ 0 ] * 30 # Column array where its indices indicates column and # used to check whether a queen can be placed in that # row or not cl = [ 0 ] * 30 # A utility function to print solution def printSolution(board): for i in range (N): for j in range (N): print (board[i][j], end = " " ) print () # A recursive utility function to solve N # Queen problem def solveNQUtil(board, col): # Base case: If all queens are placed # then return True if (col > = N): return True # Consider this column and try placing # this queen in all rows one by one for i in range (N): # Check if the queen can be placed on board[i][col] # To 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 if ((ld[i - col + N - 1 ] ! = 1 and rd[i + col] ! = 1 ) and cl[i] ! = 1 ): # Place this queen in board[i][col] board[i][col] = 1 ld[i - col + N - 1 ] = rd[i + col] = cl[i] = 1 # Recur to place rest of the queens if (solveNQUtil(board, col + 1 )): return True # If placing queen in board[i][col] # doesn't lead to a solution, # then remove queen from board[i][col] board[i][col] = 0 # BACKTRACK ld[i - col + N - 1 ] = rd[i + col] = cl[i] = 0 # If the queen cannot be placed in # any row in this column col then return False 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 1s. # Please note that there may be more than one # solutions, this function prints one of the # feasible solutions. def solveNQ(): board = [[ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 ]] if (solveNQUtil(board, 0 ) = = False ): printf( "Solution does not exist" ) return False printSolution(board) return True # Driver Code if __name__ = = '__main__' : solveNQ() # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to solve N Queen Problem using backtracking using System; class GFG { static int N = 4; // ld is an array where its indices indicate row-col+N-1 // (N-1) is for shifting the difference to store // negative indices static int [] ld = new int [30]; // 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 static int [] rd = new int [30]; // Column array where its indices indicates column and // used to check whether a queen can be placed in that // row or not static int [] cl = new int [30]; // A utility function to print solution static void printSolution( int [, ] board) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write( " {0} " , board[i, j]); Console.Write( "\n" ); } } // A recursive utility function to solve N // Queen problem static bool solveNQUtil( int [, ] board, int col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i,col] // To 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 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Place this queen in board[i,col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true ; // If placing queen in board[i,col] // doesn't lead to a solution, then // remove queen from board[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. static bool solveNQ() { int [, ] board = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false ) { Console.Write( "Solution does not exist" ); return false ; } printSolution(board); return true ; } // Driver Code public static void Main(String[] args) { solveNQ(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code to implement the approach let N = 4; // ld is an array where its indices indicate row-col+N-1 // (N-1) is for shifting the difference to store negative // indices let ld = new Array(30); // 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 let rd = new Array(30); // Column array where its indices indicates column and // used to check whether a queen can be placed in that // row or not let cl = new Array(30); // A utility function to print solution function printSolution( board) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write(board[i][j] + " " ); document.write( "<br/>" ); } } // A recursive utility function to solve N // Queen problem function solveNQUtil(board, col) { // Base case: If all queens are placed // then return true if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for (let i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] // To 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 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Place this queen in board[i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true ; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // If the queen cannot be placed in any row in // this column col then return false 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 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. function solveNQ() { let board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false ) { document.write( "Solution does not exist" ); return false ; } printSolution(board); return true ; } // Driver code solveNQ(); // This code is contributed by sanjoy_62. </script> |
. . Q . Q . . . . . . Q . Q . .
Time Complexity: O(N!)
Auxiliary Space: O(N)
Related Articles:
N Queen Problem
We have discussed Knight’s tour and Rat in a Maze problem earlier as examples of Backtracking problems. Let us discuss N Queen as another example problem that can be solved using backtracking.
Contact Us