N Queen Problem using Branch And Bound - GeeksforGeeks.pdf

Design and algorithms notes important

1. Job Fair 2024
Explore Our Geeks
Community
N Queen Problem
N-Queen in Different
languages
4 Queens Problem
8 queen problem
N Queen Problem using
Branch And Bound
N Queen in O(n) space
Printing all solutions in N-
Queen Problem
Minimum queens required
to cover all the squares of
a chess board
The N queens puzzle is the problem of placing
N chessqueens on an N×N chessboard so that no two
queens threaten each other. Thus, a solution requires
that no two queens share the same row, column, or
diagonal.
The backtracking Algorithm for N-Queen is already
discussed here. In a backtracking solution, we backtrack
when we hit a dead end. In Branch and Bound solution,
after building a partial solution, we figure out that
there is no point going any deeper as we are going to
hit a dead end. 
Let’s begin by describing the backtracking solution. “The
idea is to place queens one by one in different columns,
starting from the leftmost column. When we place a
N Queen Problem using Branch
And Bound
Read Courses Practice Jobs
DSABranch and Bound TutorialBacktracking Vs Branch-N-Bound0/1 Knapsack8 Puzzle ProblemJob Assignment ProblemN-Queen ProblemTra
Skip to contentOpen In App

2. Number of cells a queen
can move with obstacles
on the chessboard
N-Queen Problem | Local
Search using Hill climbing
with random neighbour
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.”
Skip to contentOpen In App

3. Placing 1st queen on (3, 0) and 2nd queen on (5, 1)
1. For the 1st Queen, there are total 8 possibilities as we
can place 1st Queen in any row of first column. Let’s
place Queen 1 on row 3.
2. After placing 1st Queen, there are 7 possibilities left
for the 2nd Queen. But wait, we don’t really have 7
possibilities. We cannot place Queen 2 on rows 2, 3
or 4 as those cells are under attack from Queen 1. So,
Queen 2 has only 8 – 3 = 5 valid positions left.
3. After picking a position for Queen 2, Queen 3 has
even fewer options as most of the cells in its column
are under attack from the first 2 Queens.
We need to figure out an efficient way of keeping track of
which cells are under attack. In previous solution we kept
Skip to contentOpen In App

4. an 8­-by­-8 Boolean matrix and update it each time we
placed a queen, but that required linear time to update
as we need to check for safe cells.
Basically, we have to ensure 4 things: 
1. No two queens share a column. 
2. No two queens share a row. 
3. No two queens share a top-right to left-bottom
diagonal. 
4. No two queens share a top-left to bottom-right
diagonal.
Number 1 is automatic because of the way we store the
solution. For number 2, 3 and 4, we can perform updates
in O(1) time. The idea is to keep three Boolean arrays
that tell us which rows and which diagonals are
occupied.
Lets do some pre-processing first. Let’s create two N x N
matrix one for / diagonal and other one for \ diagonal.
Let’s call them slashCode and backslashCode
respectively. The trick is to fill them in such a way that
two queens sharing a same /­diagonal will have the same
value in matrix slashCode, and if they share same \­-
diagonal, they will have the same value in
backslashCode matrix.
For an N x N matrix, fill slashCode and backslashCode
Skip to contentOpen In App

5. matrix using below formula –
slashCode[row][col] = row + col 
backslashCode[row][col] = row – col + (N-1)
Using above formula will result in below matrices 
Skip to contentOpen In App

6. The ‘N – 1’ in the backslash code is there to ensure that
the codes are never negative because we will be using
the codes as indices in an array.
Now before we place queen i on row j, we first check
whether row j is used (use an array to store row info).
Then we check whether slash code ( j + i ) or backslash
code ( j – i + 7 ) are used (keep two arrays that will tell us
which diagonals are occupied). If yes, then we have to try
a different location for queen i. If not, then we mark the
row and the two diagonals as used and recurse on queen
i + 1. After the recursive call returns and before we try
another position for queen i, we need to reset the row,
Skip to contentOpen In App

7. slash code and backslash code as unused again, like in
the code from the previous notes.
Below is the implementation of above idea –  
This code Takes the Dynamic Input:
C++
#include<bits/stdc++.h>
using namespace std;
int N;
 
 
// function for printing the solution
void printSol(vector<vector<int>>board)
{
   for(int i  = 0;i<N;i++){
       for(int j = 0;j<N;j++){
           cout<<board[i][j]<<" ";
       }
       cout<<"\n";
   }
}
 
/*  Optimized isSafe function
isSafe function to check if current row conta
 yes return false
 else return true
*/
 
bool isSafe(int row ,int col ,vector<bool>ro
{
      
   if(rows[row] == true || left_digonals[row
Skip to contentOpen In App

8.        return false;
   }
   
   return true;
}
 
// Recursive function to solve N-queen Proble
bool solve(vector<vector<int>>& board ,int c
{      
       // base Case : If all Queens are place
       if(col>=N){
           return true;
       }
 
      /* Consider this Column and move  in al
       for(int i = 0;i<N;i++)
       {
           if(isSafe(i,col,rows,left_digonals
           {
               rows[i] = true;
               left_digonals[i+col] = true;
               Right_digonals[col-i+N-1] = tr
               board[i][col] = 1;   // placin
                
                /* recur to place rest of the
 
               if(solve(board,col+1,rows,left
                   return true;
               }
                
               // Backtracking
               rows[i] = false;
               left_digonals[i+col] = false;
               Right_digonals[col-i+N-1] = fa
               board[i][col] = 0;    // remov
 
           }
Skip to contentOpen In App

9.        }
 
        return false;
}
 
 
int main()
{
   // Taking input from the user
 
   cout<<"Enter the no of rows for the square
   cin>>N;
 
 
   // board of size N*N
   vector<vector<int>>board(N,vector<int>(N,0
 
 
    // array to tell which rows are occupied
   vector<bool>rows(N,false);         
 
   // arrays to tell which diagonals are occu
   vector<bool>left_digonals(2*N-1,false);
   vector<bool>Right_digonals(2*N-1,false);
 
 
   bool ans =  solve(board , 0, rows,left_di
 
   if(ans == true){
 
       // printing the solution Board
       printSol(board);
   }
   else{
       cout<<"Solution Does not Exist\n";
   }
}
Skip to contentOpen In App

10. C
 // This Code is Contributed by Parshant Rajp
/* C++ program to solve N Queen Problem using
   and Bound */
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define N 8
 
/* 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++)
            printf("%2d ", board[i][j]);
        printf("\n");
    }
}
 
/* A Optimized function to check if a queen c
be placed on board[row][col] */
bool isSafe(int row, int col, int slashCode[
            int backslashCode[N][N], bool row
      bool slashCodeLookup[], bool backslash
{
    if (slashCodeLookup[slashCode[row][col]]
        backslashCodeLookup[backslashCode[row
        rowLookup[row])
    return false;
 
    return true;
}
Skip to contentOpen In App

11.  
/* A recursive utility function
to solve N Queen problem */
bool solveNQueensUtil(int board[N][N], int c
    int slashCode[N][N], int backslashCode[N
                                  bool rowLoo
                            bool slashCodeLoo
                           bool backslashCode
{
    /* 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 queen can be placed on
           board[i][col] */
        if ( isSafe(i, col, slashCode,
                    backslashCode, rowLookup
          slashCodeLookup, backslashCodeLooku
        {
            /* Place this queen in board[i][c
            board[i][col] = 1;
            rowLookup[i] = true;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
 
            /* recur to place rest of the que
            if ( solveNQueensUtil(board, col
                                  slashCode,
             rowLookup, slashCodeLookup, back
                return true;
 
            /* If placing queen in board[i][c
Skip to contentOpen In App

12.             doesn't lead to a solution, then
 
            /* Remove queen from board[i][col
            board[i][col] = 0;
            rowLookup[i] = false;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
        }
    }
 
    /* If queen can not be place in any row i
        this column col then return false */
    return false;
}
 
/* This function solves the N Queen problem u
Branch and Bound. It mainly uses solveNQueens
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 solveNQueens()
{
    int board[N][N];
    memset(board, 0, sizeof board);
 
    // helper matrices
    int slashCode[N][N];
    int backslashCode[N][N];
 
    // arrays to tell us which rows are occup
    bool rowLookup[N] = {false};
 
    //keep two arrays to tell us
    // which diagonals are occupied
Skip to contentOpen In App

13. Java
    bool slashCodeLookup[2*N - 1] = {false};
    bool backslashCodeLookup[2*N - 1] = {fal
 
    // initialize helper matrices
    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, backslas
      rowLookup, slashCodeLookup, backslashCo
                                             
    {
        printf("Solution does not exist");
        return false;
    }
 
    // solution found
    printSolution(board);
    return true;
}
 
// Driver program to test above function
int main()
{
    solveNQueens();
 
    return 0;
}
// Java program to solve N Queen Problem
Skip to contentOpen In App

14. // using Branch and Bound
import java.io.*;
import java.util.Arrays;
 
class GFG{
 
static int N = 8;
 
// A utility function to print solution
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
             
        System.out.printf("\n");
    }
}
 
// A Optimized function to check if a queen
// can be placed on board[row][col]
static boolean isSafe(int row, int col,
                      int slashCode[][],
                      int backslashCode[][],
                      boolean rowLookup[],
                      boolean slashCodeLookup
                      boolean backslashCodeLo
{
    if (slashCodeLookup[slashCode[row][col]]
        backslashCodeLookup[backslashCode[row
        rowLookup[row])
        return false;
 
    return true;
}
Skip to contentOpen In App

15.  
// A recursive utility function to
// solve N Queen problem
static boolean solveNQueensUtil(
    int board[][], int col, int slashCode[][
    int backslashCode[][], boolean rowLookup
    boolean slashCodeLookup[],
    boolean backslashCodeLookup[])
{
     
    // Base case: If all queens are placed
    // then return true
    int N = board.length;
     
    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 queen can be placed on bo
        if (isSafe(i, col, slashCode, backsl
                   rowLookup, slashCodeLookup
                   backslashCodeLookup))
        {
             
            // Place this queen in board[i][c
            board[i][col] = 1;
            rowLookup[i] = true;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
 
            // recur to place rest of the que
            if (solveNQueensUtil(
                    board, col + 1, slashCode
                    backslashCode, rowLookup
Skip to contentOpen In App

16.                     slashCodeLookup,
                    backslashCodeLookup))
                return true;
 
            // If placing queen in board[i][c
            // lead to a solution, then backt
 
            // Remove queen from board[i][col
            board[i][col] = 0;
            rowLookup[i] = false;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
        }
    }
 
    // If queen can not be place in any row
    // in this column col then return false
    return false;
}
 
/*
 * This function solves the N Queen problem u
 * and Bound. It mainly uses solveNQueensUtil
 * the problem. It returns false if queens ca
 * placed, otherwise return true and prints p
 * queens in the form of 1s. Please note that
 * be more than one solutions, this function
 * of the feasible solutions.
 */
static boolean solveNQueens()
{
    int board[][] = new int[N][N];
     
    // Helper matrices
    int slashCode[][] = new int[N][N];
    int backslashCode[][] = new int[N][N];
 
Skip to contentOpen In App

17.     // Arrays to tell us which rows are occup
    boolean[] rowLookup = new boolean[N];
 
    // Keep two arrays to tell us
    // which diagonals are occupied
    boolean slashCodeLookup[] = new boolean[
    boolean backslashCodeLookup[] = new bool
 
    // Initialize helper matrices
    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, rowLo
                         slashCodeLookup,
                         backslashCodeLookup
    {
        System.out.printf("Solution does not
        return false;
    }
     
    // Solution found
    printSolution(board);
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    solveNQueens();
}
}
 
Skip to contentOpen In App

18. Python3
// This code is contributed by sujitmeshram
""" Python3 program to solve N Queen Problem
using Branch or Bound """
 
N = 8
 
""" 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 Optimized function to check if
a queen can be placed on board[row][col] """
def isSafe(row, col, slashCode, backslashCode
           rowLookup, slashCodeLookup,
                       backslashCodeLookup):
    if (slashCodeLookup[slashCode[row][col]]
        backslashCodeLookup[backslashCode[row
        rowLookup[row]):
        return False
    return True
 
""" A recursive utility function
   to solve N Queen problem """
def solveNQueensUtil(board, col, slashCode, b
                     rowLookup, slashCodeLook
                     backslashCodeLookup):
                         
    """ base case: If all queens are
       placed then return True """
Skip to contentOpen In App

19.     if(col >= N):
        return True
    for i in range(N):
        if(isSafe(i, col, slashCode, backslas
                  rowLookup, slashCodeLookup
                  backslashCodeLookup)):
                     
            """ Place this queen in board[i]
            board[i][col] = 1
            rowLookup[i] = True
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
             
            """ recur to place rest of the qu
            if(solveNQueensUtil(board, col +
                                slashCode, ba
                                rowLookup, sl
                                backslashCode
                return True
             
            """ If placing queen in board[i]
            doesn't lead to a solution,then b
             
            """ Remove queen from board[i][co
            board[i][col] = 0
            rowLookup[i] = False
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
             
    """ If queen can not be place in any row
    this column col then return False """
    return False
 
""" This function solves the N Queen problem
Branch or Bound. It mainly uses solveNQueensU
solve the problem. It returns False if queens
cannot be placed,otherwise return True or
Skip to contentOpen In App

20. 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 solveNQueens():
    board = [[0 for i in range(N)]
                for j in range(N)]
     
    # helper matrices
    slashCode = [[0 for i in range(N)]
                    for j in range(N)]
    backslashCode = [[0 for i in range(N)]
                        for j in range(N)]
     
    # arrays to tell us which rows are occupi
    rowLookup = [False] * N
     
    # keep two arrays to tell us
    # which diagonals are occupied
    x = 2 * N - 1
    slashCodeLookup = [False] * x
    backslashCodeLookup = [False] * x
     
    # initialize helper matrices
    for rr in range(N):
        for cc in range(N):
            slashCode[rr][cc] = rr + cc
            backslashCode[rr][cc] = rr - cc
     
    if(solveNQueensUtil(board, 0, slashCode,
                        rowLookup, slashCodeL
                        backslashCodeLookup)
        print("Solution does not exist")
        return False
         
    # solution found
    printSolution(board)
Skip to contentOpen In App

21. C#
    return True
 
# Driver Code
solveNQueens()
 
# This code is contributed by SHUBHAMSINGH10
using System;
using System.Linq;
 
class GFG {
  static int N = 8;
 
  // 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.WriteLine();
    }
  }
 
  // A Optimized function to check if a queen
  // can be placed on board[row][col]
  static bool isSafe(int row, int col, int[,
                     int[, ] backslashCode,
                     bool[] rowLookup,
                     bool[] slashCodeLookup,
                     bool[] backslashCodeLook
  {
    if (slashCodeLookup[slashCode[row, col]]
Skip to contentOpen In App

22.         || backslashCodeLookup[backslashCode
        || rowLookup[row])
      return false;
 
    return true;
  }
 
  // A recursive utility function to
  // solve N Queen problem
  static bool solveNQueensUtil(int[, ] board
                               int[, ] slashC
                               int[, ] backsl
                               bool[] rowLook
                               bool[] slashCo
                               bool[] backsla
  {
 
    // 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 queen can be placed on boar
      if (isSafe(i, col, slashCode, backslash
                 rowLookup, slashCodeLookup,
                 backslashCodeLookup)) {
 
        // Place this queen in board[i][col]
        board[i, col] = 1;
        rowLookup[i] = true;
        slashCodeLookup[slashCode[i, col]] =
        backslashCodeLookup[backslashCode[i,
          = true;
 
Skip to contentOpen In App

23.         // recur to place rest of the queens
        if (solveNQueensUtil(
          board, col + 1, slashCode,
          backslashCode, rowLookup,
          slashCodeLookup,
          backslashCodeLookup))
          return true;
 
        // If placing queen in board[i][col]
        // lead to a solution, then backtrack
 
        // Remove queen from board[i][col]
        board[i, col] = 0;
        rowLookup[i] = false;
        slashCodeLookup[slashCode[i, col]] =
        backslashCodeLookup[backslashCode[i,
          = false;
      }
    }
 
    // If queen can not be place in any row
    // in this column col then return false
    return false;
  }
 
  /*
     * This function solves theN Queen proble
     * and Bound. It mainly uses solveNQueens
     * the problem. It returns false if queen
     * placed, otherwise return true and prin
     * queens in the form of 1s. Please note
     * be more than one solutions, this funct
     * of the feasible solutions.
     */
  static bool solveNQueens()
  {
    int[, ] board = new int[N, N];
Skip to contentOpen In App

24.     // Helper matrices
    int[, ] slashCode = new int[N, N];
    int[, ] backslashCode = new int[N, N];
 
    // Arrays to tell us which rows are occup
    bool[] rowLookup = new bool[N];
 
    // Keep two arrays to tell us
    // which diagonals are occupied
    bool[] slashCodeLookup = new bool[2 * N
    bool[] backslashCodeLookup = new bool[2
 
    // Initialize helper arrays
    for (int r = 0; r < N; r++) {
      for (int c = 0; c < N; c++) {
        slashCode[r, c] = r + c;
        backslashCode[r, c] = r - c + N - 1;
      }
    }
 
    if (!solveNQueensUtil(board, 0, slashCode
                          backslashCode, rowL
                          slashCodeLookup,
                          backslashCodeLookup
      Console.WriteLine("Solution does not ex
      return false;
    }
 
    printSolution(board);
    return true;
  }
 
  // Driver code
  public static void Main() { solveNQueens()
}
 
// This code is contributed by lokeshpotta20
Skip to contentOpen In App

25. Javascript
 
// JavaScript program to solve N Queen Proble
// using Branch and Bound
 
let N = 8;
 
// A utility function to print solution
function printSolution(board)
{
    let N = board.length;
    for(let i = 0; i < N; i++)
    {
        for(let j = 0; j < N; j++)
            document.write(board[i][j]+" ");
              
        document.write("<br>");
    }
}
 
// A Optimized function to check if a queen
// can be placed on board[row][col]
function isSafe(row,col,slashCode,backslashCo
{
    if (slashCodeLookup[slashCode[row][col]]
        backslashCodeLookup[backslashCode[row
        rowLookup[row])
        return false;
  
    return true;
}
 
// A recursive utility function to
// solve N Queen problem
Skip to contentOpen In App

26. function solveNQueensUtil(board,col,slashCode
backslashCode,rowLookup,slashCodeLookup,backs
{
    // Base case: If all queens are placed
    // then return true
    //let N = board.length;
      
    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 queen can be placed on bo
        if (isSafe(i, col, slashCode, backsl
                   rowLookup, slashCodeLookup
                   backslashCodeLookup))
        {
              
            // Place this queen in board[i][c
            board[i][col] = 1;
            rowLookup[i] = true;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
  
            // recur to place rest of the que
            if (solveNQueensUtil(
                    board, col + 1, slashCode
                    backslashCode, rowLookup
                    slashCodeLookup,
                    backslashCodeLookup))
                return true;
  
            // If placing queen in board[i][c
            // lead to a solution, then backt
  
Skip to contentOpen In App

27.             // Remove queen from board[i][col
            board[i][col] = 0;
            rowLookup[i] = false;
            slashCodeLookup[slashCode[i][col
            backslashCodeLookup[backslashCode
        }
    }
  
    // If queen can not be place in any row
    // in this column col then return false
    return false;
}
 
/*
 * This function solves the N Queen problem u
 * and Bound. It mainly uses solveNQueensUtil
 * the problem. It returns false if queens ca
 * placed, otherwise return true and prints p
 * queens in the form of 1s. Please note that
 * be more than one solutions, this function
 * of the feasible solutions.
 */
function solveNQueens()
{
    let board = new Array(N);
      
    // Helper matrices
    let slashCode = new Array(N);
    let backslashCode = new Array(N);
      
    for(let i=0;i<N;i++)
    {
        board[i]=new Array(N);
        slashCode[i]=new Array(N);
        backslashCode[i]=new Array(N);
        for(let j=0;j<N;j++)
        {
Skip to contentOpen In App

28.             board[i][j]=0;
            slashCode[i][j]=0;
            backslashCode[i][j]=0;
        }
    }
     
     
    // Arrays to tell us which rows are occup
    let rowLookup = new Array(N);
     for(let i=0;i<N;i++)
        rowLookup[i]=false;
     
    // Keep two arrays to tell us
    // which diagonals are occupied
    let slashCodeLookup = new Array(2 * N -
    let backslashCodeLookup = new Array(2 * N
     for(let i=0;i<2*N-1;i++)
    {
        slashCodeLookup[i]=false;
        backslashCodeLookup[i]=false;
    }
  
    // Initialize helper matrices
    for(let r = 0; r < N; r++)
        for(let c = 0; c < N; c++)
        {
            slashCode[r] = r + c;
            backslashCode[r] = r - c + 7;
        }
  
    if (solveNQueensUtil(board, 0, slashCode
                         backslashCode, rowLo
                         slashCodeLookup,
                         backslashCodeLookup
    {
        document.write("Solution does not exi
        return false;
Skip to contentOpen In App

29. Learn Data Structures & Algorithms with GeeksforGeeks
Input:
Enter the no of rows for the square Board : 8
Output :
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
    }
      
    // Solution found
    printSolution(board);
    return true;
}
 
// Driver code
solveNQueens();
 
 
// This code is contributed by avanitrachhadi
 
Skip to contentOpen In App

30. The time and space complexity of the N-Queen
problem solver implemented in the provided code are:
Time Complexity: The time complexity of the solver
algorithm is O(N!), where N is the number of rows and
columns in the square board. This is because for each
column, the algorithm tries to place a queen in each row
and then recursively tries to place the queens in the
remaining columns. The number of possible
combinations of queen placements in the board is N!
since there can be only one queen in each row and each
column.
Space Complexity: The space complexity of the solver
algorithm is O(N^2), where N is the number of rows and
columns in the square board. This is because we are
using a 2D vector to represent the board, which takes up
N^2 space. Additionally, we are using three boolean
arrays to keep track of the occupied rows and diagonals,
which take up 2N-1 space each. Therefore, the total
space complexity is O(N^2 + 6N – 3), which is equivalent
to O(N^2).
References :
https://en.wikipedia.org/wiki/Eight_queens_puzzle
www.cs.cornell.edu/~wdtseng/icpc/notes/bt2.pdf
Skip to contentOpen In App

31. "The DSA course helped me a lot in clearing the
interview rounds. It was really very helpful in setting a
strong foundation for my problem-solving skills. Really a
great investment, the passion Sandeep sir has towards
DSA/teaching is what made the huge difference."
- Gaurav | Placed at Amazon
Before you move on to the world of
development, master the fundamentals of DSA on
which every advanced algorithm is built upon. Choose
your preferred language and start learning today: 
DSA In JAVA/C++
DSA In Python
DSA In JavaScript
Trusted by Millions, Taught by One- Join the best DSA
Course Today!
Recommended Problems
Frequently asked DSA Problems
Solve Problems
Skip to contentOpen In App

32. Similar Reads
8 puzzle Problem using
Branch And Bound
Job Assignment Problem
using Branch And Bound
Traveling Salesman
Problem using Branch And
Bound
Find position of Queen in
chessboard from given
attack lines of queen
Generate Binary Strings of
length N using Branch and
Bound
Implementation of 0/1
Knapsack using Branch
and Bound
Get paid for your published articles and stand a chance
to win tablet, smartwatch and exclusive GfG goodies!
Submit your entries in Dev Scripter 2024 today.
Last Updated : 20 Sep, 2023
Share your thoughts in the
comments
24
Previous
8 queen problem
Next
N Queen in O(n) space
Add Your Comment
Skip to contentOpen In App

33. A-143, 9th Floor, Sovereign Corporate
Tower, Sector-136, Noida, Uttar Pradesh -
201305
Company
About Us
Legal
Careers
In Media
Contact Us
Advertise with
us
Explore
Job-A-Thon
Hiring
Challenge
Hack-A-Thon
GfG Weekly
Contest
Python
Java
C++
PHP
GoLang
SQL
Data
Structures
Algorithms
DSA for
Beginners
Basic DSA
Problems
Data
Science &
ML
Data Science
With Python
Data Science
For Beginner
HTML
CSS
Web Templates
CSS
Frameworks
Bootstrap
Tailwind CSS
LanguagesDSA HTML & CSS
0/1 Knapsack using Least
Cost Branch and Bound
0/1 Knapsack using
Branch and Bound
Difference between
Backtracking and Branch-
N-Bound technique
Branch and Bound
meaning in DSA
Aditya Goel
Article Tags :chessboard-problems,Branch and Bound,
DSA
A
Additional Information
Skip to contentOpen In App

34. GFG Corporate
Solution
Placement
Training
Program
Offline Classes
(Delhi/NCR)
DSA in
JAVA/C++
Master System
Design
Master CP
GeeksforGeeks
Videos
Geeks
Community
R Language
Android
Tutorial
Tutorials
Archive
DSA Roadmap
Top 100 DSA
Interview
Problems
DSA Roadmap
by Sandeep
Jain
All Cheat
Sheets
Machine
Learning
Tutorial
ML Maths
Data
Visualisation
Tutorial
Pandas
Tutorial
NumPy
Tutorial
NLP Tutorial
Deep Learning
Tutorial
SASS
LESS
Web Design
Python
Programming
Examples
Django Tutorial
Python
Projects
Python Tkinter
Web Scraping
GATE CS Notes
Operating
Systems
Computer
Network
Database
Management
System
Git
AWS
Docker
Kubernetes
Azure
GCP
DevOps
Roadmap
Top DS or Algo
for CP
Top 50 Tree
Top 50 Graph
Top 50 Array
Top 50 String
Top 50 DP
High Level
Design
Low Level
Design
UML Diagrams
Interview
Guide
Design
Patterns
JavaScript
Examples
TypeScript
ReactJS
NextJS
AngularJS
NodeJS
Lodash
Web Browser
Python Computer
Science
DevOps Competitive
Programming
System
Design
JavaScript
Skip to contentOpen In App

35. OpenCV
Python
Tutorial
Python
Interview
Question
Software
Engineering
Digital Logic
Design
Engineering
Maths
Top 15
Websites for
CP
OOAD
System Design
Bootcamp
Interview
Questions
NCERT
Solutions
Class 12
Class 11
Class 10
Class 9
Class 8
Complete
Study Material
School
Subjects
Mathematics
Physics
Chemistry
Biology
Social Science
English
Grammar
Accountancy
Business
Studies
Economics
Management
HR
Management
Finance
Income Tax
UPSC Study
Material
Polity Notes
Geography
Notes
History Notes
Science and
Technology
Notes
Economy
Notes
Ethics Notes
Previous Year
Papers
SSC/
BANKING
SSC CGL
Syllabus
SBI PO
Syllabus
SBI Clerk
Syllabus
IBPS PO
Syllabus
IBPS Clerk
Syllabus
SSC CGL
Practice Papers
Indian Colleges
Admission &
Campus
Experiences
List of Central
Universities -
In India
Colleges in
Delhi
University
IIT Colleges
NIT Colleges
IIIT Colleges
META Owned
Companies
Exams
JEE Mains
JEE Advanced
More
Tutorials
Free Online
Tools
Typing Test
Write &
Earn
Write an Article
Commerce Colleges
CompaniesPreparation
Corner
Skip to contentOpen In App

36. Alphabhet
Owned
Companies
TATA Group
Owned
Companies
Reliance
Owned
Companies
Fintech
Companies
EdTech
Companies
Company-Wise
Recruitment
Process
Resume
Templates
Aptitude
Preparation
Puzzles
Company-Wise
Preparation
GATE CS
NEET
UGC NET
Software
Development
Software
Testing
Product
Management
SAP
SEO - Search
Engine
Optimization
Linux
Excel
Image Editor
Code
Formatters
Code
Converters
Currency
Converter
Random
Number
Generator
Random
Password
Generator
Improve an
Article
Pick Topics to
Write
Share your
Experiences
Internships
@GeeksforGeeks, Sanchhaya Education Private Limited, All rights reservedOpen In App