# N-Queen Problem

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.

We will use the backtracking concept to place all

Nqueens in theN*Nchessboard 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:The

Time Complexityfor the above backtracking algorithm isExponential (n^n).C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: