The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回 n 皇后不同的解决方案的数量。
Example:
Input
: 4
Output
: 2
Explanation
: There are two distinct solutions to the
4-queens puzzle as shown below
.
[
[".Q..",
"...Q",
"Q...",
"..Q."],
["..Q.",
"Q...",
"...Q",
".Q.."]
]
C++
class Solution {
public:
int totalNQueens(int n
) {
board
= vector
<string
>(n
,string(n
,'.'));
cols
= vector
<int>(n
,0);
diag1
= vector
<int>(2 * n
- 1, 0);
diag2
= vector
<int>(2 * n
- 1, 0);
backtrack(n
, 0);
return cnt
;
}
private:
vector
<string
> board
;
vector
<int> cols
;
vector
<int> diag1
;
vector
<int> diag2
;
int cnt
;
bool available(int x
, int y
, int n
){
return !cols
[x
]
&& !diag1
[x
+y
]
&& !diag2
[x
- y
+ n
-1];
}
void update(int x
, int y
, int n
, bool isput
){
cols
[x
] = isput
;
diag1
[x
+y
] = isput
;
diag2
[x
- y
+ n
-1] = isput
;
board
[x
][y
] = isput
? 'Q' : '.';
}
void backtrack(int n
, int y
){
if(y
== n
){
cnt
++;
return;
}
for(int x
= 0; x
< n
; x
++){
if(!available(x
,y
,n
)) continue;
update(x
,y
,n
,true);
backtrack(n
,y
+1);
update(x
,y
,n
,false);
}
}
};
C++ ②
class Solution {
public:
int cnt
;
vector
<int> cols
;
vector
<int> diag1
;
vector
<int> diag2
;
vector
<string
>board
;
int totalNQueens(int n
) {
cnt
= 0;
cols
= vector
<int> (n
, 0);
diag1
= vector
<int> (2*n
-1, 0);
diag2
= vector
<int> (2*n
-1, 0);
board
= vector
<string
> (n
,string(n
,'.'));
backtrack(n
,0);
return cnt
;
}
bool available(int x
, int y
, int n
){
return !cols
[x
] && !diag1
[x
+y
] && !diag2
[x
- y
+ n
- 1];
}
void update(int x
, int y
, int n
, bool isput
){
cols
[x
] = isput
;
diag1
[x
+y
] = isput
;
diag2
[x
-y
+n
-1] = isput
;
board
[x
][y
] = isput
? 'Q' : '.';
}
void backtrack(int n
,int y
){
if(y
== n
){
cnt
++;
return;
}
for(int x
= 0; x
< n
; x
++){
if(!available(x
,y
,n
)) continue;
update(x
, y
, n
, true);
backtrack(n
,y
+1);
update(x
, y
, n
, false);
}
}
};
小结：是前一题的子问题LeetCode 51. N-Queens，直接copy上一题的代码，最后输出cnt即可。
