# N Queen Problem | Return all Distinct Solutions to the N-Queens Puzzle

Problem Statement: The n-queens is the problem of placing n queens on n × n chessboard such that no two queens can attack each other. Given an integer n, return all distinct solutions to the n -queens puzzle. Each solution contains a distinct boards configuration of the queen’s placement, where ‘Q’ and ‘.’ indicate queen and empty space respectively.

```Examples:

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown below
```

Let us first understand how can we place queens in a chessboard so that no attack on either of them can take place.

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Intuition: Using the concept of Backtracking, we will place Queen at different positions of the chessboard and find the right arrangement where all the n queens can be placed on the n*n grid.

Approach:

Ist position: This is the position where we can see no possible arrangement is found where all queens can be placed since, at the 3rd column, the Queen will be killed at all possible positions of row.

2nd position: One of the correct possible arrangements is found. So we will store it as our answer.

3rd position: One of the correct possible arrangements is found. So we will store it as our answer.

4th position: This is the position where we can see no possible arrangement is found where all queens can be placed since, at the 4th column, the Queen will be killed at all possible positions of row.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;
class Solution {
public:
bool isSafe1(int row, int col, vector < string > board, int n) {
// check upper element
int duprow = row;
int dupcol = col;

while (row >= 0 && col >= 0) {
if (board[row][col] == 'Q')
return false;
row--;
col--;
}

col = dupcol;
row = duprow;
while (col >= 0) {
if (board[row][col] == 'Q')
return false;
col--;
}

row = duprow;
col = dupcol;
while (row < n && col >= 0) {
if (board[row][col] == 'Q')
return false;
row++;
col--;
}
return true;
}

public:
void solve(int col, vector < string > & board, vector < vector < string >> & ans, int n) {
if (col == n) {
ans.push_back(board);
return;
}
for (int row = 0; row < n; row++) {
if (isSafe1(row, col, board, n)) {
board[row][col] = 'Q';
solve(col + 1, board, ans, n);
board[row][col] = '.';
}
}
}

public:
vector < vector < string >> solveNQueens(int n) {
vector < vector < string >> ans;
vector < string > board(n);
string s(n, '.');
for (int i = 0; i < n; i++) {
board[i] = s;
}
solve(0, board, ans, n);
return ans;
}
};
int main() {
int n = 4; // we are taking 4*4 grid and 4 queens
Solution obj;
vector < vector < string >> ans = obj.solveNQueens(n);
for (int i = 0; i < ans.size(); i++) {
cout << "Arrangement " << i + 1 << "\n";
for (int j = 0; j < ans[0].size(); j++) {
cout << ans[i][j];
cout << endl;
}
cout << endl;
}
return 0;
}``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature, since we are trying out all ways. To be precise it goes as O

(N! * N) nearly.

Space Complexity: O(N^2)

## Java Code

``````import java.util.*;
class TUF {
public static List < List < String >> solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
List < List < String >> res = new ArrayList < List < String >> ();
dfs(0, board, res);
return res;
}

static boolean validate(char[][] board, int row, int col) {
int duprow = row;
int dupcol = col;
while (row >= 0 && col >= 0) {
if (board[row][col] == 'Q') return false;
row--;
col--;
}

row = duprow;
col = dupcol;
while (col >= 0) {
if (board[row][col] == 'Q') return false;
col--;
}

row = duprow;
col = dupcol;
while (col >= 0 && row < board.length) {
if (board[row][col] == 'Q') return false;
col--;
row++;
}
return true;
}

static void dfs(int col, char[][] board, List < List < String >> res) {
if (col == board.length) {
return;
}

for (int row = 0; row < board.length; row++) {
if (validate(board, row, col)) {
board[row][col] = 'Q';
dfs(col + 1, board, res);
board[row][col] = '.';
}
}
}

static List < String > construct(char[][] board) {
List < String > res = new LinkedList < String > ();
for (int i = 0; i < board.length; i++) {
String s = new String(board[i]);
}
return res;
}
public static void main(String args[]) {
int N = 4;
List < List < String >> queen = solveNQueens(N);
int i = 1;
for (List < String > it: queen) {
System.out.println("Arrangement " + i);
for (String s: it) {
System.out.println(s);
}
System.out.println();
i += 1;
}

}
}``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature since we are trying out all ways, to be precise its O(N! * N).

Space Complexity: O( N2 )

## Python Code

``````class Solution:
def isSafe1(self, row, col, board, n):
# check upper element
duprow = row
dupcol = col

while row >= 0 and col >= 0:
if board[row][col] == 'Q':
return False
row -= 1
col -= 1

col = dupcol
row = duprow
while col >= 0:
if board[row][col] == 'Q':
return False
col -= 1

row = duprow
col = dupcol
while row < n and col >= 0:
if board[row][col] == 'Q':
return False
row += 1
col -= 1

return True

def solve(self, col, board, ans, n):
if col == n:
ans.append(list(board))
return

for row in range(n):
if self.isSafe1(row, col, board, n):
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
self.solve(col+1, board, ans, n)
board[row] = board[row][:col] + '.' + board[row][col+1:]

def solveNQueens(self, n):
ans = []
board = ['.'*n for _ in range(n)]
self.solve(0, board, ans, n)
return ans

n = 4
obj = Solution()
ans = obj.solveNQueens(n)
for i in range(len(ans)):
print(f"Arrangement {i+1}")
for j in range(len(ans[0])):
print(ans[i][j])
print()``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature since we are trying out all ways, to be precise its O(N! * N).

Space Complexity: O( N2 )

Solution 2:

Intuition: This is the optimization of the issafe function. In the previous issafe function, we need o(N) for a row, o(N) for the column, and o(N) for the diagonal. Here, we will use hashing to maintain a list to check whether that position can be the right one or not.

Approach:

For checking Left row elements

For checking upper diagonal and lower diagonal

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;
class Solution {
public:
void solve(int col, vector < string > & board, vector < vector < string >> & ans, vector < int > & leftrow, vector < int > & upperDiagonal, vector < int > & lowerDiagonal, int n) {
if (col == n) {
ans.push_back(board);
return;
}
for (int row = 0; row < n; row++) {
if (leftrow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[n - 1 + col - row] == 0) {
board[row][col] = 'Q';
leftrow[row] = 1;
lowerDiagonal[row + col] = 1;
upperDiagonal[n - 1 + col - row] = 1;
solve(col + 1, board, ans, leftrow, upperDiagonal, lowerDiagonal, n);
board[row][col] = '.';
leftrow[row] = 0;
lowerDiagonal[row + col] = 0;
upperDiagonal[n - 1 + col - row] = 0;
}
}
}

public:
vector < vector < string >> solveNQueens(int n) {
vector < vector < string >> ans;
vector < string > board(n);
string s(n, '.');
for (int i = 0; i < n; i++) {
board[i] = s;
}
vector < int > leftrow(n, 0), upperDiagonal(2 * n - 1, 0), lowerDiagonal(2 * n - 1, 0);
solve(0, board, ans, leftrow, upperDiagonal, lowerDiagonal, n);
return ans;
}
};
int main() {
int n = 4; // we are taking 4*4 grid and 4 queens
Solution obj;
vector < vector < string >> ans = obj.solveNQueens(n);
for (int i = 0; i < ans.size(); i++) {
cout << "Arrangement " << i + 1 << "\n";
for (int j = 0; j < ans[0].size(); j++) {
cout << ans[i][j];
cout << endl;
}
cout << endl;
}
return 0;
}``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature since we are trying out all ways, to be precise it is O(N! * N).

Space Complexity: O(N)

## Java Code

``````import java.util.*;
class TUF {
public static List < List < String >> solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
List < List < String >> res = new ArrayList < List < String >> ();
int leftRow[] = new int[n];
int upperDiagonal[] = new int[2 * n - 1];
int lowerDiagonal[] = new int[2 * n - 1];
solve(0, board, res, leftRow, lowerDiagonal, upperDiagonal);
return res;
}

static void solve(int col, char[][] board, List < List < String >> res, int leftRow[], int lowerDiagonal[], int upperDiagonal[]) {
if (col == board.length) {
return;
}

for (int row = 0; row < board.length; row++) {
if (leftRow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[board.length - 1 + col - row] == 0) {
board[row][col] = 'Q';
leftRow[row] = 1;
lowerDiagonal[row + col] = 1;
upperDiagonal[board.length - 1 + col - row] = 1;
solve(col + 1, board, res, leftRow, lowerDiagonal, upperDiagonal);
board[row][col] = '.';
leftRow[row] = 0;
lowerDiagonal[row + col] = 0;
upperDiagonal[board.length - 1 + col - row] = 0;
}
}
}

static List < String > construct(char[][] board) {
List < String > res = new LinkedList < String > ();
for (int i = 0; i < board.length; i++) {
String s = new String(board[i]);
}
return res;
}
public static void main(String args[]) {
int N = 4;
List < List < String >> queen = solveNQueens(N);
int i = 1;
for (List < String > it: queen) {
System.out.println("Arrangement " + i);
for (String s: it) {
System.out.println(s);
}
System.out.println();
i += 1;
}

}
}``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature since we are trying out all ways, to be precise its O(N! * N).

Space Complexity: O(N)

## Python Code

``````from typing import List

class Solution:
def solve(self, col, board, ans, leftrow, upperDiagonal, lowerDiagonal, n):
if col == n:
ans.append(board[:])
return

for row in range(n):
if leftrow[row] == 0 and lowerDiagonal[row+col] == 0 and upperDiagonal[n-1+col-row] == 0:
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
leftrow[row] = 1
lowerDiagonal[row+col] = 1
upperDiagonal[n-1+col-row] = 1
self.solve(col+1, board, ans, leftrow,
upperDiagonal, lowerDiagonal, n)
board[row] = board[row][:col] + '.' + board[row][col+1:]
leftrow[row] = 0
lowerDiagonal[row+col] = 0
upperDiagonal[n-1+col-row] = 0

def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = ['.'*n for _ in range(n)]
leftrow = [0]*n
upperDiagonal = [0]*(2*n-1)
lowerDiagonal = [0]*(2*n-1)
self.solve(0, board, ans, leftrow, upperDiagonal, lowerDiagonal, n)
return ans

if __name__ == '__main__':
n = 4
obj = Solution()
ans = obj.solveNQueens(n)
for i in range(len(ans)):
print("Arrangement", i+1)
for j in range(len(ans[0])):
print(ans[i][j])
print()``````

Output:

Arrangement 1
..Q.
Q…
…Q
.Q..

Arrangement 2
.Q..
…Q
Q…
..Q.

Time Complexity: Exponential in nature since we are trying out all ways, to be precise it is O(N! * N).

Space Complexity: O(N)