N-Queen

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, we will discuss the N queens problem. The N-queen problem is one of the most common and practical examples to understand Backtracking.

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 - 

 

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.

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 none of the positions left is safe. So, this is not the desired configuration.

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

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 - 

  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(044, 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)

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] = {{0000},
                      {0000},
                      {0000},
                      {0000}};

    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 Complexity -  O(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.

Frequently Asked Questions

1.  What is backtracking?

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

2.  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.
3.  In chess, in how many directions a queen can attack?

A queen can attack in 3 directions - horizontally, vertically and diagonally.
4. 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.

Key Takeaways

In this article, we learnt to solve the famous N queen problem using backtracking. If you want to master backtracking, learn Backtracking here. 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.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

 

Was this article helpful ?
0 upvotes