N-Queen Problem - Naukri Code 360

Introduction

The N-Queen Problem is a fascinating and classic puzzle that has captivated mathematicians, computer scientists, and puzzle enthusiasts for decades. First formulated in the 19th century, the problem involves placing N queens on an N×N chessboard in such a way that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.

The elegance of the N-Queen Problem lies in its simplicity and the depth of the challenge it presents. While the rules are straightforward, the solutions require careful consideration and strategic placement of each queen. The problem scales with N, offering an increasing level of complexity and a rich field for exploration in algorithm design and optimization. In this blog, we will explore N-Queen Problem.

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

What is the N-Queen problem?

The N-Queen Problem is a classic puzzle in computer science and mathematics. The goal of the N-Queen Problem is to place N queens on an N×N chessboard so that no two queens can attack each other. This means ensuring that no two queens share the same row, column, or diagonal.

Problem Statement

You are given an integer N. For a given N x N 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.

N-Queen Problem Using 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 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 -

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 N 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

Start with the first row.
Check the number of queens placed. If it is N, then return true.
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.

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

Implementation

C++

/*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;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class NQueen {

    static boolean isSafe(int row, int col, int[][] board, int N) {
        int i, j;

        // Check this column on upper side
        for (i = 0; i < row; i++)
            if (board[i][col] == 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 upper diagonal on right side
        for (i = row, j = col; i >= 0 && j < N; i--, j++)
            if (board[i][j] == 1)
                return false;

        return true;
    }

    static boolean solveNQUtil(int row, int nQueens, int N, int[][] board) {
        if (nQueens == 0)
            return true;

        for (int col = 0; col < N; col++) {
            if (isSafe(row, col, board, N)) {
                board[row][col] = 1;
                if (solveNQUtil(row + 1, nQueens - 1, N, board))
                    return true;
                board[row][col] = 0; // backtracking
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int N = 4;
        int[][] board = new int[N][N];

        solveNQUtil(0, N, N, board);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                System.out.print(board[i][j] + "\t");
            System.out.println();
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def is_safe(row, col, board, N):
    for i in range(row):
        if board[i][col] == 1:
            return False

    i, j = row, col
    while i >= 0 and j < N:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1

    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1

    return True

def solve_n_queen(row, n_queens, N, board):
    if n_queens == 0:
        return True

    for col in range(N):
        if is_safe(row, col, board, N):
            board[row][col] = 1
            if solve_n_queen(row + 1, n_queens - 1, N, board):
                return True
            board[row][col] = 0  # backtracking

    return False

if __name__ == "__main__":
    N = 4
    board = [[0] * N for _ in range(N)]
    solve_n_queen(0, N, N, board)

    for row in board:
        print("\t".join(map(str, row)))

You can also try this code with Online Python Compiler

Run Code

Javascript

function isSafe(row, col, board, N) {
    for (let i = 0; i < row; i++)
        if (board[i][col] === 1) return false;

    for (let i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j] === 1) return false;

    for (let i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] === 1) return false;

    return true;
}

function solveNQueen(row, nQueens, N, board) {
    if (nQueens === 0) return true;

    for (let col = 0; col < N; col++) {
        if (isSafe(row, col, board, N)) {
            board[row][col] = 1;
            if (solveNQueen(row + 1, nQueens - 1, N, board)) return true;
            board[row][col] = 0; // backtracking
        }
    }

    return false;
}

(function main() {
    const N = 4;
    const board = Array.from({ length: N }, () => Array(N).fill(0));
    solveNQueen(0, N, N, board);

    board.forEach(row => {
        console.log(row.join("\t"));
    });
})();

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

public class NQueen
{
    static bool IsSafe(int row, int col, int[,] board, int N)
    {
        for (int i = 0; i < row; i++)
            if (board[i, col] == 1)
                return false;

        for (int i = row, j = col; i >= 0 && j < N; i--, j++)
            if (board[i, j] == 1)
                return false;

        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i, j] == 1)
                return false;

        return true;
    }

    static bool SolveNQueen(int row, int nQueens, int N, int[,] board)
    {
        if (nQueens == 0)
            return true;

        for (int col = 0; col < N; col++)
        {
            if (IsSafe(row, col, board, N))
            {
                board[row, col] = 1;
                if (SolveNQueen(row + 1, nQueens - 1, N, board))
                    return true;
                board[row, col] = 0; // backtracking
            }
        }

        return false;
    }

    public static void Main()
    {
        int N = 4;
        int[,] board = new int[N, N];
        SolveNQueen(0, N, N, board);

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                Console.Write(board[i, j] + "\t");
            Console.WriteLine();
        }
    }
}

PHP

<?php

function isSafe($row, $col, $board, $N) {
    for ($i = 0; $i < $row; $i++) {
        if ($board[$i][$col] == 1) return false;
    }

    for ($i = $row, $j = $col; $i >= 0 && $j < $N; $i--, $j++) {
        if ($board[$i][$j] == 1) return false;
    }

    for ($i = $row, $j = $col; $i >= 0 && $j >= 0; $i--, $j--) {
        if ($board[$i][$j] == 1) return false;
    }

    return true;
}

function solveNQueen($row, $nQueens, $N, &$board) {
    if ($nQueens == 0) return true;

    for ($col = 0; $col < $N; $col++) {
        if (isSafe($row, $col, $board, $N)) {
            $board[$row][$col] = 1;
            if (solveNQueen($row + 1, $nQueens - 1, $N, $board)) return true;
            $board[$row][$col] = 0; // backtracking
        }
    }

    return false;
}

$N = 4;
$board = array_fill(0, $N, array_fill(0, $N, 0));
solveNQueen(0, $N, $N, $board);

for ($i = 0; $i < $N; $i++) {
    for ($j = 0; $j < $N; $j++) {
        echo $board[$i][$j] . "\t";
    }
    echo "\n";
}

?>

You can also try this code with Online PHP Compiler

Run Code

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).

N-Queen Problem Using Optimized Backtracking

Points to consider for optimization -

We will not check every cell of the right and left diagonals to determine if a cell is safe.
The idea is to use the property of diagonals.
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.
This will reduce the cost of checking if the cell is safe from O(N) to O(1).

Implementation

C++

/*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);
    }
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class NQueenProblem {

    static final int N = 4;
    static int[] leftDiagonal = new int[30];
    static int[] rightDiagonal = new int[30];
    static int[] column = new int[30];

    static boolean nQueen(int[][] board, int col) {
        if (col >= N)
            return true;

        for (int row = 0; row < N; row++) {
            if (leftDiagonal[row - col + N - 1] != 1 &&
                    rightDiagonal[row + col] != 1 &&
                    column[row] != 1) {

                board[row][col] = 1;
                leftDiagonal[row - col + N - 1] = 1;
                rightDiagonal[row + col] = 1;
                column[row] = 1;

                if (nQueen(board, col + 1))
                    return true;

                board[row][col] = 0;
                leftDiagonal[row - col + N - 1] = 0;
                rightDiagonal[row + col] = 0;
                column[row] = 0;
            }
        }

        return false;
    }

    static void printBoard(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                System.out.print(board[i][j] + "\t");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[N][N];

        if (!nQueen(board, 0)) {
            System.out.println("No valid configuration exists");
        } else {
            printBoard(board);
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

N = 4
leftDiagonal = [0] * 30
rightDiagonal = [0] * 30
column = [0] * 30

def n_queen(board, col):
    if col >= N:
        return True
    
    for row in range(N):
        if leftDiagonal[row - col + N - 1] != 1 and rightDiagonal[row + col] != 1 and column[row] != 1:
            board[row][col] = 1
            leftDiagonal[row - col + N - 1] = 1
            rightDiagonal[row + col] = 1
            column[row] = 1
            
            if n_queen(board, col + 1):
                return True
            
            board[row][col] = 0
            leftDiagonal[row - col + N - 1] = 0
            rightDiagonal[row + col] = 0
            column[row] = 0
    
    return False

def print_board(board):
    for row in board:
        print("\t".join(map(str, row)))

board = [[0] * N for _ in range(N)]

if not n_queen(board, 0):
    print("No valid configuration exists")
else:
    print_board(board)

You can also try this code with Online Python Compiler

Run Code

Javascript

const N = 4;
let leftDiagonal = new Array(30).fill(0);
let rightDiagonal = new Array(30).fill(0);
let column = new Array(30).fill(0);

function nQueen(board, col) {
    if (col >= N)
        return true;

    for (let row = 0; row < N; row++) {
        if (leftDiagonal[row - col + N - 1] !== 1 &&
            rightDiagonal[row + col] !== 1 &&
            column[row] !== 1) {

            board[row][col] = 1;
            leftDiagonal[row - col + N - 1] = 1;
            rightDiagonal[row + col] = 1;
            column[row] = 1;

            if (nQueen(board, col + 1))
                return true;

            board[row][col] = 0;
            leftDiagonal[row - col + N - 1] = 0;
            rightDiagonal[row + col] = 0;
            column[row] = 0;
        }
    }

    return false;
}

function printBoard(board) {
    for (let i = 0; i < N; i++) {
        console.log(board[i].join("\t"));
    }
}

let board = new Array(N).fill(0).map(() => new Array(N).fill(0));

if (!nQueen(board, 0)) {
    console.log("No valid configuration exists");
} else {
    printBoard(board);
}

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

public class NQueenProblem {
    const int N = 4;
    static int[] leftDiagonal = new int[30];
    static int[] rightDiagonal = new int[30];
    static int[] column = new int[30];

    static bool nQueen(int[,] board, int col) {
        if (col >= N)
            return true;

        for (int row = 0; row < N; row++) {
            if (leftDiagonal[row - col + N - 1] != 1 &&
                rightDiagonal[row + col] != 1 &&
                column[row] != 1) {

                board[row, col] = 1;
                leftDiagonal[row - col + N - 1] = 1;
                rightDiagonal[row + col] = 1;
                column[row] = 1;

                if (nQueen(board, col + 1))
                    return true;

                board[row, col] = 0;
                leftDiagonal[row - col + N - 1] = 0;
                rightDiagonal[row + col] = 0;
                column[row] = 0;
            }
        }

        return false;
    }

    static void printBoard(int[,] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                Console.Write(board[i, j] + "\t");
            Console.WriteLine();
        }
    }

    public static void Main() {
        int[,] board = new int[N, N];

        if (!nQueen(board, 0)) {
            Console.WriteLine("No valid configuration exists");
        } else {
            printBoard(board);
        }
    }
}

PHP

<?php
const N = 4;
$leftDiagonal = array_fill(0, 30, 0);
$rightDiagonal = array_fill(0, 30, 0);
$column = array_fill(0, 30, 0);

function nQueen(&$board, $col) {
    if ($col >= N)
        return true;

    global $leftDiagonal, $rightDiagonal, $column;

    for ($row = 0; $row < N; $row++) {
        if ($leftDiagonal[$row - $col + N - 1] != 1 &&
            $rightDiagonal[$row + $col] != 1 &&
            $column[$row] != 1) {

            $board[$row][$col] = 1;
            $leftDiagonal[$row - $col + N - 1] = 1;
            $rightDiagonal[$row + $col] = 1;
            $column[$row] = 1;

            if (nQueen($board, $col + 1))
                return true;

            $board[$row][$col] = 0;
            $leftDiagonal[$row - $col + N - 1] = 0;
            $rightDiagonal[$row + $col] = 0;
            $column[$row] = 0;
        }
    }

    return false;
}

function printBoard($board) {
    foreach ($board as $row) {
        echo implode("\t", $row) . "\n";
    }
}

$board = array_fill(0, N, array_fill(0, N, 0));

if (!nQueen($board, 0)) {
    echo "No valid configuration exists\n";
} else {
    printBoard($board);
}
?>

You can also try this code with Online PHP Compiler

Run Code

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 N rows and N columns.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

What is the N-Queen problem in artificial intelligence?

The N-Queen problem in artificial intelligence involves placing N queens on an N×N chessboard such that no two queens threaten each other.

What is the importance of N-Queen problem in real life?

The N-Queen problem is crucial for developing and testing algorithms in constraint satisfaction, optimization, and backtracking, with applications in scheduling and resource allocation.

What is the time complexity of n queens?

The time complexity of the N-Queen problem is O(N!), due to the factorial number of ways to arrange the queens on the board.

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, N times, for N 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 Maze, The 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.