八皇后问题

n−n−皇后问题是指将nn 个皇后放在 n×n``n×n 的国际象棋棋盘上, 使得皇后不能相互攻击到, 即任意两个皇后都不能处于同一行, 同一列或同一斜线上

这道题目有两种分析情况，我先来分析第一种。

设变量

#include<iostream>
using namespace std;
const int N = 20;
int n;
bool col[N], dg[N], udg[N];
char g[N][N];

首先，我们要知道皇后在每一行，每一列，每一斜列都不可以遇到一样的皇后，那么我们不妨创立三种变量来表示竖向的，左斜方向的，右斜方向的三个bool数组来分析，同时我们要创立一盘棋，用char变量来表示

摆棋

这样我们就可以把变量创建出来了，第二步就是摆上一盘棋

int main()
{
	cin >> n;
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			g[i][j] = '.';
	dfs(0);
	return 0;
}

bfs解法

现在开始我们就可以来分析这道题的dfs问题解法了

​ 这种方法是对于每一行进行依次枚举, 看看这一行的哪个格子是否满足情况，符合的话我们就把皇后插进去.

for (int i = 0; i < n; i++)
	{
		if (!col[i] && !dg[u + i] && !udg[n - u + i])
		{
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
	}

注意: 上述的n指的是有几行, u指的是第一列(数组上的表示是0),我们假设n是3

​ 我们一步步分析, 开始col[0]是ture，代表这一行是没有放皇后的，dg[u+i]和udg[n-u+1]也是一样，都没有插入任何一个数，所以我们把第一个皇后插入g[0][0],那么对应的col[0]变成true,dg[0]和udg[3]也变成了true,此后进入下一个dfs循环.

​ 下一个进来后，u的值变成1了，现在是在第二行, g[1][0]直接排除.第二行的col[1]和dg[2]是可以过的，但是我们想想就知道，g[1][1]是不可以塞皇后的，所以我们不还有最后一层保险吗，我们的udg[3]是true，它不允许我们的皇后插进去，所以u只能最后去走走g[1][2],终于三个都不挡住它了,我们可以进入下一个dfs了.

​ 第三层中,我们的u是2，它先走到g[2][0]上面, col[0]=true,dg[2]=false,udg[1]=false是不能放的，到g[2][1]的时候也是放不了皇后的, g[2][2]一样放不了，这波直接出for循环了，根据dfs的性质，我们如果都不满足会回到上一个dfs中，但是由于我们在回到上一步dfs的时候有一些数值变了，那我们就要恢复原来改变的数值，甚至可能全部推翻。

找到解

​ 最后我们终于找到了一个解,那我们就直接把解输出出来.

if (u == n)
	{
		for (int i = 0; i < n; i++) puts(g[i]);
		puts("");
		return;
	}

return是返回上一个dfs节点上，可能会有多个解法出现

在3的时候是没有解的, hh

引入

—acwing算法基础课 (yxc主讲)