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 n-queens’ placement, where 'Q'
and '.'
both indicate a queen and an empty space, respectively.
Example:
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 above
Table of Contents
N-Queens Problem Solution
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');
solution.add(line0.toString());
}
result.add(solution);
} 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;
}