N-Queens Problem
Description
LeetCode Problem 51.
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 1:
1
2
3
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
Example 2:
1
2
Input: n = 1
Output: [["Q"]]
Constraints:
- 1 <= n <= 9
Sample C++ Code
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
vector<vector<string>> sols;
int N;
void dfs(vector<int>& col2row, int row) {
if (row == N) {
vector<string> sol;
string s;
for (int i = 0; i < N; i ++) {
s = "";
for (int j = 0; j < N; j ++) {
if (col2row[j] == i)
s += 'Q';
else
s += '.';
}
sol.push_back(s);
}
sols.push_back(sol);
return;
}
vector<vector<int>> dir = { {-1,-1}, {1,1}, {-1,1}, {1,-1} };
for (int i = 0; i < N; i ++) {
if (col2row[i] == -1) {
int r = row, c = i;
bool place = true;
for (int j = 0; j < 4; j ++) {
r = row+dir[j][0], c = i+dir[j][1];
while (r >= 0 && c >= 0 && r < N && c < N && place) {
if (col2row[c] == r) {
place = false; break;
}
r += dir[j][0], c += dir[j][1];
}
if (!place)
break;
}
if (place) {
col2row[i] = row;
dfs(col2row, row+1);
col2row[i] = -1;
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
N = n;
vector<int> col2row(n, -1);
dfs(col2row, 0);
return sols;
}
};