This problem is to place n number of queens on a chessboard such that, no two queens attack each other. Return all the solutions.

Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

## Introduction:

A queen in a chess board can move it her left, right and diagonal.

Then, if we have a “n * n” matrix with “n” queens, we need to place the 4 queens in such a way that they won’t kill each other.

If we wanted to find an optimal solution, we need to go for dynamic programming. Here we just need to find the ways to place the queens, hence we shall discuss backtracking.

Let us take an example of 4 * 4 board and a queen is placed in (1, 2) as shown in the diagram below:

Hence the queen can move in below directions:

row: [1, 0], [1, 1], [1, 3] column: [0, 2], [2, 2], [3, 2] diagonal 1: [0, 1], [2, 3] diagonal 2: [3, 0], [2, 1], [0, 3]

Hence from the above table, we can deduce that,

1. A new queen placed in row 1 will be attacked,

2. A new queen placed in column 2 will be attacked.

Then we have 2 diagonals.

1. Diagonal 1 is going from top left to bottom right.

2. Diagonal 2 is going from bottom left to top right.

For diagonal 1, we use [row – column]. I.e [1 – 2] = -1. Hence if any row column value is -1, that cell will be attacked by the queen.

For diagonal 2, we use [row + column]. I.e [1 + 2] = 3. Hence if any row column value is 3, that cell will be attacked by the queen.

**How do we find the solution to the problem?**

We solve it by backtracking. Since we are using 4 * 4 matrix, our recursion will be 4 level deep.

First, we place a queen in [0, 0]. Then we place the 2^{nd} queen such that it is not attacked by the first queen by using RECURSION. It can be shown as below:

The matrix is shown below:

Now, we try to place the 3^{rd} queen, but we don’t have a safe place to place the 3^{rd} queen as it can be attacked by other 2 queens. Hence the recursion function will return false as shown below:

Hence, we backtrack to 2^{nd} queen and try to place it in next position and try to place the 3^{rd} queen. Hence we place the 3^{rd} queen in box 1.

Now while placing the 4^{th} queen, there is no safe place. Hence the recursion function will return false to 3^{rd} queen.

And the queen 3 will also return false to 2^{nd} queen, as it cannot find the safe place.

2^{nd} queen will return false to 1^{st} queen as it cannot find a safe place.

Now queen 1 has to be moved. Once we place the queen 1 in 1^{st} box, we get the solution as shown below.

## The solution in CPP:

#include<iostream> #include<vector> using namespace std; bool Isvalid(vector<int> &a, int k) { for (int i = 0; i < k; i++) { if (abs(k - i) == abs(a[i] - a[k]) || a[i] == a[k]) { return false; } } return true; } void Backtrack(vector<vector<string> > &answers, vector<string> &answer, vector<int> &a, int deep) { if (deep >= answer.size()) { answers.push_back(answer); return; } else { for (int j = 0; j < answer[deep].size(); j++) { a[deep] = j; if (Isvalid(a, deep)) { answer[deep][j] = 'Q'; Backtrack(answers, answer, a, deep + 1); answer[deep][j] = '.'; } } } } vector<vector<string> > solveNQueens(int n) { vector<vector<string> > answers; vector<int> a(n, 0); vector<string> answer(n, string(n, '.')); Backtrack(answers, answer, a, 0); return answers; } int main() { int n = 4; vector<vector<string> > output = solveNQueens(n); for (int i = 0; i < output.size(); i++) { for (int j = 0; j < output[0].size(); j++) { cout<< output[i][j]<<" "; } cout<<endl; } }

## Output:

.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..