N-Queens

Desicription

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

fuck

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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

1
2
3
4
5
6
7
8
9
10
11
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
private:
vector<vector<string>> res;
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> state(n, -1);
dfs(state, 0);
return res;
}
void dfs(vector<int>& state, int row){
int n = state.size();
if(row == n){
vector<string> tmp(n, string(n, '.'));
for(int i = 0; i < n; i++)
tmp[i][state[i]] = 'Q';
res.push_back(tmp);
return ;
}
for(int col = 0; col < n; col++){
if(isVaild(state, row, col)){
state[row] = col;
dfs(state, row+1);
state[row] = -1;
}
}
}
bool isVaild(vector<int>& state, int row, int col){
for(int i = 0; i < row; i++){
if(state[i] == col || abs(row - i) == abs(col - state[i]))
return 0;
}
return 1;
}
};