# Leetcode N-Queens problem solution

In this Leetcode N-Queens problem solution, The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the queen's placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

## Problem solution in Python.

```class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.n = n
res = []
self.backtrack(0,[],res)
return res

def backtrack(self, row, pList, res):
if row == self.n:
res.append(['.'*x+'Q'+'.'*(self.n-1-x) for x in pList])
return
if row > self.n:
return
for col in range(self.n):
if self.check(col, row, pList):
self.backtrack(row+1, pList+[col], res)

def check(self, col, row, pList):
for r in range(row):
if pList[r] == col or row-r == abs(col-pList[r]):
return False
return True
```

## Problem solution in Java.

```class Solution {

StringBuilder line = new StringBuilder();

void f(List<List<String>> result, int[] s, int i, int n, boolean x[]) {
if (i == n) {
List<String> solution = new ArrayList<>();
for (int k = 0; k < n; k++) {
StringBuilder line0 = new StringBuilder(line);
line0.insert(s[k], 'Q');
}
} else {
for (int j = 0; j < n; j++) {
int p1 = j - i + 2 * n - 1;
int p2 = i + j + 3 * n - 2;
if (!x[j] && !x[p1] && !x[p2]) {
boolean[] x0 = new boolean[x.length]; System.arraycopy(x, 0, x0, 0, x.length);
int[] s0 = new int[n]; System.arraycopy(s, 0, s0, 0, n);
x0[j] = x0[p1] = x0[p2] = true;
s0[i] = j;
f(result, s0, i + 1, n, x0);
}
}
}
}

public List<List<String>> solveNQueens(int n) {
if(n==2 || n==3) return new ArrayList<>();
for (int i = 0; i < n - 1; i++) line.append('.');
List<List<String>> result = new ArrayList<>();
f(result, new int[n], 0, n, new boolean[5 * n - 2]);
return result;
}

}
```

## Problem solution in C++.

```class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> rt;
vector<int> vc, vs(2*n-1,-1), vd(2*n-1,-1);
for( int i=0; i<n; i++) vc.push_back(i);

dfs( 0, vc, vs, vd, rt);

return rt;
}

void dfs( int j, vector<int>& vc, vector<int>& vs, vector<int>& vd, vector<vector<string>>& rt){
if(j==vc.size())    pushQ( vc, rt);

for( int i=j, t; i<vc.size(); i++){
t=vc[i];
vc[i]=vc[j];
vc[j]=t;

if(vs[vc[j]+j]==-1&&vd[vc[j]-j+vc.size()-1]==-1){
vs[vc[j]+j]=1;
vd[vc[j]-j+vc.size()-1]=1;

dfs( j+1, vc, vs, vd, rt);

vs[vc[j]+j]=-1;
vd[vc[j]-j+vc.size()-1]=-1;
}

t=vc[i];
vc[i]=vc[j];
vc[j]=t;
}

return ;
}

void pushQ( vector<int>& vc, vector<vector<string>>& rt){
string s(vc.size(),'.');
vector<string> vs(vc.size(),s);

for( int i=0; i<vc.size(); i++) vs[i][vc[i]]='Q';

rt.push_back(vs);

return ;
}

};
```

## Problem solution in C.

```typedef struct Queens {
char ***queens[1000];
int count;
}Queens, *pQueens;

void nqueen (int row, int n, int *res, pQueens Q);
void save (int n, int *res, pQueens Q);
bool check (int row, int *res);

char*** solveNQueens(int n, int* returnSize) {
if (n < 1 || returnSize == NULL)
return NULL;
pQueens Q = (pQueens) calloc(1, sizeof(Queens));
int res[n];
memset(res, 0, sizeof(res));
nqueen (0, n, &res, Q);
*returnSize = Q->count;
return Q->queens;
}

void nqueen (int row, int n, int *res, pQueens Q) {
if (row == n){
save(n, res, Q);
return;
}
for (int i = 0; i < n; ++i) {
res[row] = i;
if (check(row, res))
nqueen(row + 1, n, res, Q);
}
}

void save (int n, int *res, pQueens Q) {
char **matrix = (char **) malloc(n * sizeof(char *));
for (int i = 0; i < n; ++i) {
matrix[i] = (char *) calloc((n + 1), sizeof(char));
int j;
for (j = 0; j < n; ++j) {
matrix[i][j] = '.';
}
matrix[i][res[i]] = 'Q';
}
*(Q->queens + Q->count) = matrix;
++Q->count;
return;
}

bool check (int row, int *res) {
for (int i = 0; i < row; ++i) {
if (res[row] == res[i] || abs(res[row] - res[i]) == (row - i))
return false;
}
return true;
}
```