843. n-皇后问题
求解n皇后问题实质上也是一种深度遍历,因为对于棋盘上每一个格子,都会有不同的情况需要判断(行/列/对角线),这就类似于树的分支
与数字排列的思想类似,我们需要找到一组符合条件的摆放,
n=4
.Q..
...Q
Q...
..Q.
n=8
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....
所有满足条件的皇后数与棋盘规模n相等(s==n)
然后对这些皇后Q进行排列,前提是必须满足一定条件,即:任意两个Q不在同一行/列/主对角线/反对角线上
所以我们要做的就是从第一个格子开始进行遍历:给定”四个分支”的数组:row[]/col[]/dia[]/udia[],若遍历到一个格子时,它的行/列对角线上元素为空(即row[]/col[]/dia[]/udia[]四个数组为空),那么这个格子就合法,可以摆放皇后。
作者:crayongrq
链接:https://www.acwing.com/solution/content/179688/
#include<iostream>
using namespace std;
const int N = 10;
//定义棋盘大小n*n
int n;
char g[N][N];
//行数row=N, 列数col=N,与主对角线平行的条数dia=2N-1,与反对角线平行的条数udia=2N-1
int row[N], col[N], dia[N * 2], udia[N * 2];
//s代表格子中已摆放的皇后的个数
void dfs(int x, int y, int s){
//从上面第一行开始,从左往右逐个遍历格子,如果越界,则重新从下一行开始遍历
if(y == n){
y = 0;
x ++;
}
//此时遍历到了最后一行s==n,代表满足条件的皇后已经放完,即找到了一组满足条件的解
if(x == n){
if(s == n){
// 按行输出棋盘情况-——二维数组输出第i行元素:g[i]
for (int i = 0; i < n; i ++) cout << g[i] << endl;
cout << endl;
}
return;
}
//判断当前格子是否满足放入皇后的条件
//dia[x - y + n]/udia[x + y] 用对角线的截距来表示当前格子的下标
//由于只是判断当前格子是否在满足了条件后且为空,所以只需保证数组下标不为负数即可,加上偏移量:dia[x - y + n]
if(row[x] == 0 && col[y] == 0 && dia[x - y + n] == 0 && udia[x + y] == 0){
//在棋盘格(x,y)处放入皇后Q
g[x][y] = 'Q';
//标记与该格子相关联的行/列/对角线/反对角线 已经放入了一个满足条件的皇后
row[x] = col[y] = dia[x - y + n] = udia[x + y] = true;
//放入皇后,s+1,继续深度遍历下一个格子
dfs(x, y + 1, s + 1);
//恢复现场
row[x] = col[y] = dia[x - y + n] = udia[x + y] = false;
g[x][y] = '.';
//由于上一次情况已经判断完毕,因此恢复现场要重置格子为'.'
}
//这里用到了"剪枝优化"的思想:即row[x] == 0 && col[y] == 0 && dia[x - y + n] == 0 && udia[x + y] == 0
//其中有一个条件不满足,就不再继续向下遍历,因为再向下遍历的结果肯定不合法
//该格不放皇后,继续深度遍历下一个格子
dfs(x, y + 1, s);
}
int main(){
cin >> n;
//初始化棋盘
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++)
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}