题目描述
八皇后问题,大家都懂
关键点
y总视频里面讲得非常清楚了,和全排列问题一模一样,只是多了剪枝操作,所以八皇后问题的关键就是理解这个剪枝是怎么个剪法!
把整个棋盘看作一个二维坐标系,行就是纵坐标Y,列就是横坐标X,分别对应代码里面的,u和i,同一对角线上面的所有点的横纵坐标都满足该对角线的直线方程,红色的对角线方程是y = -x + b,绿色的对角线方程是 y = x + b;
用u 和 i 来表示就是,u = - i + b; u = i + b;所以,到了这里大家就看出来了,当遍历到某个点(u,i)的时候,要判断它正对角线和反对角线是否有其他元素,就可以利用dg[]数组和udg[]数组,为了防止出现负数,udg[]数组里面整体做了n的正偏移;
C++ 代码
#include<iostream>
using namespace std;
int count;
const int N = 10;
int n;
char path[N][N];
bool col[N],dg[N*2],udg[N*2];
void dfs(int u){
if(u == n){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
cout<<path[i][j];
}
cout<<endl;
}
cout<<endl;
return ;
}
for(int i = 0;i<n;i++){
if(col[i] == false && dg[u+i] == false && udg[n+i-u] == false){
path[u][i] = 'Q';
col[i] = dg[u+i] = udg[n+i-u] = true;
dfs(u+1);
col[i] = dg[u+i] = udg[n+i-u] = false;
path[u][i] = '.';
}
}
}
int main(){
cin>>n;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
path[i][j] = '.';
}
}
dfs(0);
return 0;
}