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, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:

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

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

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 wont 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,

A new queen placed in row 1 will be attacked,

A new queen placed in column 2 will be attacked.

Then we have 2 diagonals.

Diagonal 1 is going form top left to bottom right.
Diagonal 2 is going form 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 for 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 2nd 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 3rd queen, but we don’t have a safe place to place the 3rd queen as it can be attacked by other 2 queens. Hence the recursion function will return false as shown below:

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

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

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

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

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

 

/*
* File     : n_queens.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;
	}
}