题解 | N皇后问题
N皇后问题
https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6
#include <utility>
class Solution {
public:
int k = 0;
vector<pair<int, int>> memo;
bool legal(int dep, int col, int n){ // 行数，列数，棋盘宽度
int x, y;
for(int i=0; i<memo.size(); i++){
x = memo[i].first;
y = memo[i].second;
if(dep==x || col==y || dep-x==col-y || x+y==dep+col)
return false;
}
return true;
}
void dfs(int dep, int n){
if(dep==n){
k++;
return ;
}
for(int i=0; i<n; i++){
if(legal(dep, i, n)){
memo.push_back(std::make_pair(dep, i));
dfs(dep+1, n);
memo.pop_back();
}
}
}
int Nqueen(int n) {
dfs(0, n);
return k;
}
};
思路：
1.1、设深度为dep，同时也可以理解为现在的树到了棋盘的第几行了（假设棋盘的一行与树的一层相对应）。
1.2、设可能性有k种。
2、dfs截止条件：如果dep==n，则返回。比如n=4，则说明0123这四行已经落子，现在来到了第4行，必须截止了。此时，k++。
3、对于树的每一层（棋盘的每一行），for遍历所有可能的坐标 [dep, col]，用函数 legal 判断在该坐标落子是否合法。
合法：则将该落子记到memo中；dfs(下行，即dep+1)；将该落子从memo中去掉。（for会继续往后遍历可能的坐标）
不合法：啥都不做（for会继续往后遍历可能的坐标）
4、legal函数（传过来一个当前正在考虑的坐标i，j）
我们已经将当前所有落子都记录到了memo里面。比如memo=[[0,1], [1,3], ....]
遍历所有落子，如果与当前情况（i，j）处于“同一行 / 同一列 / 同一向左斜的斜边 / 同一向右斜的斜边”，则return false。
所有memo中的落子都不与（i，j）冲突，return true；
假设memo中的坐标为xy，则：
同一行：x=i；
同一列：y=j；
同一向右斜的斜边：x-i == y-j；
同一向左斜的斜边：x+y == i+j；
查看7道真题和解析