Home » Interview coding problems/challenges

N-Queen Problem

N-Queen Problem: The N queen problem is the problem of placing N chess queens on N*N chessboard so that no two queens attack each other. You need to determine the possible arrangement.
Submitted by Divyansh Jaipuriyar, on August 20, 2020

Problem statement

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, print all distinct solutions to the n-queens puzzle.

Problem description

Given problem requires knowledge of backtracking concept since we are required to print all possible arrangements where the queen can attack other queen or it is safe so there are two possibilities for each position hence we need to use that approach. You should also keep in mind that the queen can attack in all eight directions and the index bound for given test cases.

Input

The first line of the input consist of T number of test cases, each test case consist of an integer N denoting the size of Chess board (N*N) in which we have to place Queens.

Output

Print the all possible arrangement of the Queens, each part if a segment should be either 1 denoting queen or 0 denoting not queen and if it is impossible to place them print -1.

Examples

Input:
T=1
N=4

Output:
0 1 0 0 
0 0 0 1 
1 0 0 0 
0 0 1 0 

0 0 1 0 
1 0 0 0 
0 0 0 1 
0 1 0 0 
Following are the two possible arrangements for 4*4 chessboard.

Input:
T=1
N=3

Output:
-1,
as it is not possible to form any arrangement in which 
it is possible to place queens without attacking each other.

Solution Approach

We will use the backtracking concept to place all N queens in the N*N chessboard such that none of them attack each other.

We will start placing the queen from the first row, after placing the queen in the first row we will recursively check all the remaining rows if they lead to some possible solution or not. If the current arrangement doesn't give valid configuration then we backtrack.

Backtracking Algorithm:

1. Start from the leftmost column
2. Check if the given configuration places all the queens correctly then return true.
3. Check for all the rows in the current column whether other queens are present or not
4. If the queen can be placed in the current row and column then mark this row and column as 1 and recursively check if it gives valid configuration or not. If it gives the correct solution then print the configuration.
5. If given row and column doesn't give correct solution then unmark this row and column and backtrack, repeat steps 4 and 5.
6. If all possible rows are checked and it doesn't return true then simply return false.

The Time Complexity for the above backtracking algorithm is Exponential (n^n).

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//boolean flag for checking
//valid is configuration is
//possible or not.
bool flag;

//issafe function for checking
//valid is placing in row r and col c
//is valid or not.
bool issafe(ll r, ll c, ll n, vector<vector<ll> >& v1)
{
    //check for other queen in other row
    //of current column.
    for (ll i = 0; i < r; i++) {
        if (v1[i][c])
            return false;
    }

    //check for diagonal elements '\' in this
    //format which are before current row and col.
    for (ll i = r, j = c; i >= 0 and j >= 0; i--, j--) {
        if (v1[i][j])
            return false;
    }

    //check for other diagonal elements '/' in h=this
    //format which are before current row and
    //ahead of current column.
    for (ll i = r, j = c; i >= 0 and j < n; i--, j++) {
        if (v1[i][j])
            return false;
    }

    //if no queens are placed then
    //return true.
    return true;
}

//queen function which will take row value
//as main input for placing different different queens.
void queen(vector<vector<ll> >& v1, ll r, ll n)
{
    //if we successfully placed all queens.
    if (r == n) {
        flag = true;
        //print possible arrangement.
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                if (v1[i][j])
                    cout << 1 << " ";
                else
                    cout << 0 << " ";
            }
            cout << "\n";
        }
        cout << "\n";
        return;
    }

    //check for other columns in current row.
    for (ll i = 0; i < n; i++) {
        //check validity
        if (issafe(r, i, n, v1)) {
            //mark current position.
            v1[r][i] = 1;
            //recur for other rows.
            queen(v1, r + 1, n);
            //unmark current position.
            v1[r][i] = 0;
        }
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter N: ";
        cin >> n;

        vector<vector<ll> > v1(n, vector<ll>(n, 0));
        flag = false;
        queen(v1, 0, n);

        if (flag == false)
            cout << -1 << "\n";
        else
            cout << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter N: 4
0 1 0 0 
0 0 0 1 
1 0 0 0 
0 0 1 0 

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


Enter N: 2
-1
Enter N: 1
1