Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Backtracking
2.2.
C++ Implementation
3.
Optimized Backtracking
3.1.
C++ Implementation
4.
Frequently Asked Questions
4.1.
What is backtracking?
4.2.
When is backtracking used?
4.3.
In chess, in how many directions a queen can attack?
4.4.
What is the worst-case time complexity of the brute force approach to solving the N queen problem?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

N-Queen

Author Yukti Kumari
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Backtracking and Recursion

Introduction

The N-queen problem is one of the most popular problems to get an idea of how backtracking works. Backtracking in one of the most popular concepts that is asked about in the interviews for big tech companies as well. The N-queen problem is one of the most common and practical examples to understand Backtracking.

Also see, Data Structures

Please try to solve this problem on your own before moving on to further discussion here.

Problem Statement

You are given an integer N. For a given chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.

A queen can be attacked when it lies in the same row, column, or the same diagonal as any of the other queens. You have to print one such configuration.

Print a binary matrix as output that has 1s for the cells where queens are placed.

Backtracking

Cells that can be attacked by a queen is shown below - 

Illustration Image

 

Let’s take an example to understand the requirement.

Say, N=4. Now, we will try to place the 4 queens such that each of them is safe from every other queen.

Board

In this figure, the red cross mark represents the cells that the queens can attack. 

Observe that with this arrangement, we can only place 3 queens, and the 4th queen can't be placed as any of the positions left is safe. So, this is not the desired configuration.

Let’s try to place the queens in some other way - 

Board

Hence, the valid configuration is -

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0

Note: There can be more than one such valid configuration. In this problem, our goal is just to print one of those.

The key idea is that no two queens can be placed in:

  • Same Row
  • Same Column
  • Same Diagonal
     

There are rows, so we will place one queen in each row(as no two queens can be in the same column) such that they all are safe from each other.

We will use backtracking to solve the problem. It is a recursive approach in which we place the queen at a safe position and then recur for the remaining queens. If at any step the number of queens to be placed is not zero and there are no safe cells left, then we change the position of the previously placed queen and try another safe position.

Let’s see backtracking the approach step by step - 

Check out Backtracking and Recursion

  1. Start with the first row.
  2. Check the number of queens placed. If it is N, then return true.
  3. Check all the columns for the current row one by one.
    1. If the cell [row, column] is safe then mark this cell and recursively call the function for the remaining queens to find if it leads to the solution. 

If it leads to the solution, return true, else unmark the cell [row, column] ( that is, backtrack) and check for the next column.

  1. If the cell [row, column] is not safe, skip the current column and check for the next one.
  2. If none of the cells in the current row is safe, then return false.

C++ Implementation

/*C++ code to solve N queen problem by backtracking*/
#include <bits/stdc++.h>
using namespace std;

/*function to check if a cell[i][j] is safe from attack of other queens*/
bool isSafe(int i, int j, int board[4][4], int N)
{
    int k, l;
    // checking for column j
    for (k = 0; k <= i - 1; k++)
    {
        if (board[k][j] == 1)
            return 0;
    }

    // checking upper right diagonal
    k = i - 1;
    l = j + 1;
    while (k >= 0 && l < N)
    {
        if (board[k][l] == 1)
            return 0;
        k = k + 1;
        l = l + 1;
    }

    // checking upper left diagonal
    k = i - 1;
    l = j - 1;
    while (k >= 0 && l >= 0)
    {
        if (board[k][l] == 1)
            return 0;
        k = k - 1;
        l = l - 1;
    }

    return 1; //the cell[i][j] is safe
}

int n_queen(int row, int numberOfqueens, int N, int board[4][4])
{
    if (numberOfqueens == 0)
        return 1;

    int j;
    for (j = 0; j < N; j++)
    {
        if (isSafe(row, j, board, N))
        {
            board[row][j] = 1;

            if (n_queen(row + 1, numberOfqueens - 1, N, board))
                return 1;

            board[row][j] = 0; //backtracking
        }
    }
    return 0;
}

int main()
{
    int board[4][4];
    int i, j;

    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
            board[i][j] = 0;
    }

    n_queen(0, 4, 4, board);

    //printing the board
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
            cout << board[i][j] << "\t";
        cout << endl;
    }
    return 0;
}

 

Output

0       1       0       0
0       0       0       1
1       0       0       0
0       0       1       0

 

 

Time Complexity -  O(N!)

For the first row, we check N columns; for the second row, we check the N - 1 column and so on. Hence, the time complexity will be N * (N-1) * (N-2) …. i.e. O(N!)

Space Complexity - O(N^2)

O(N^2), where ‘N’ is the number of queens.

 We are using a 2-D array of size N rows and N columns, and also, because of Recursion, the recursive stack will have a linear space here. So, the overall space complexity will be O(N^2).

Read More - Time Complexity of Sorting Algorithms 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Backtracking

Points to consider for optimization - 

  1. We will not check every cell of the right and left diagonals to determine if a cell is safe.
  2. The idea is to use the property of diagonals.
  3. For an element with row=i and column=j:
    1. The Sum of i and j is constant for each right diagonal.
    2. The difference of i and j is constant for each left diagonal.
  4. This will reduce the cost of checking if the cell is safe from O(N) to O(1).

C++ Implementation

/*C++ code to solve N queen problem by optimized backtracking approach*/
#include <bits/stdc++.h>
using namespace std;
#define N 4

/* leftDiagonal is an array where its indices indicate row-col+N-1 */
int leftDiagonal[30] = {0};
/* rightDiagonal is an array where its indices indicate row+col */
int rightDiagonal[30] = {0};
/* column array where its indices indicate column and */
int column[30] = {0};

bool n_queen(int board[N][N], int col)
{

    if (col >= N) //if all N queens are placed
        return true;

    for (int row = 0; row < N; row++)
    {
        /*check if position (row,col) is safe */
        if ((leftDiagonal[row - col + N - 1] != 1 &&
            rightDiagonal[row + col] != 1) &&
            column[row] != 1)
        {

            board[row][col] = 1; //mark the current cell
            /* mark the rightDiagonal, leftDiagonal and the column as unsafe*/
            leftDiagonal[row - col + N - 1] =
                rightDiagonal[row + col] = column[row] = 1;

            if (n_queen(board, col + 1)) /*recur for remaining queens*/
                return true;             /* if placing the queen at (row,col) leads to valid
                                            configuration then return true */

            board[row][col] = 0; /* if valid configuration is not found,
                                    backtrack and unmark the cell */
            leftDiagonal[row - col + N - 1] =
                rightDiagonal[row + col] = column[row] = 0;
        }
    }

    return false;
}

/* Function to print the board*/
void printBoard(int board[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout << board[i][j] << "\t";
        cout << "\n";
    }
}

int main()
{
    int board[N][N] = {{0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0}};

    if (n_queen(board, 0) == false)
    {
        cout << "No valid configuration exists\n";
    }
    else
    {
        printBoard(board);
    }
}

 

Output

0       0       1       0
1       0       0       0
0       0       0       1
0       1       0       0

 

Time ComplexityO(N!)

O(N!), where ‘N’ is the number of queens and ‘!’ represents factorial.

For the first row, we check ‘N’ columns, for the second row, we check the N - 1 column and so on. Hence time complexity will be N * (N-1) * (N-2) …. i.e. N!

Space Complexity - O(N^2)

O(N^2), where ‘N’ is the number of queens as we are using a 2-D array having rows and columns.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

What is backtracking?

Backtracking is an algorithmic technique to solve problems recursively and remove those solutions that do not satisfy the problem constraints at any point in time.

When is backtracking used?

It is generally used in problems where you have multiple options and after choosing one option, you have a set of new options hence recursion. The process continues until a final state or the desired state is reached.

In chess, in how many directions a queen can attack?

A queen can attack in 3 directions - horizontally, vertically, and diagonally.

What is the worst-case time complexity of the brute force approach to solving the N queen problem?

The worst-case “brute force” solution for the N-queens puzzle has an O(N^N) time complexity. This means it will look through every position on an NxN board, times, for queens.

Conclusion

In this article, we learned to solve the famous N queen problem using backtracking. If you want to master backtracking, learn Backtracking here. You can also read How to Solve 8 Queens Problem Using Backtracking. We also analyzed the time and space complexity of the approach along with its implementation. Further, we also saw the optimized backtracking approach.

Do check out Rat in MazeThe Knight’s tour problems which are also based on backtracking.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass