著名的n皇后问题
即在棋盘上任意两个皇后不能在同一行，同一列，或者斜对角线，反斜对角线的位置
以判断（5，1）位置为例
往右下方（斜对角线）一连串的位置 （5，1）（6，2）（7，3）（8，4），（x，y）得到规律
x-y=4 横纵坐标差值相等，与（5，1）5-1==4相等
得到结论（i-a[i]==x-y）
往右上方（反斜对角线）一连串的位置 （5，1）（4，2）（3，3）（2，4），（1，5），（x，y）得到规律
x+y=6 横纵坐标差值相等，与（5，1）5+1==6相等
得到结论（i+a[i]==x+y）
i从1不断遍历到n行，
a[i]表示第i行上的皇后放于a[i]列上
check函数中x、y表示 第x行的皇后可否存储在第y列上
#include<cstdio>
#include<cstdlib>
#include<iostream>//a[i]表示第i行上的皇后放于a[i]列上
using namespace std;//假设a[i]=k,则a[i]表示第i行的皇后存储在第k列的位置上
const int N=10;
int a[N];
int cnt,n;
bool check(int x,int y)//判断在10行10列的棋盘上，第x行的皇后可否存储在第y列上
{for(int i=1;i<=x;i++)//行从第一行的皇后开始遍历，以每一个皇后为关键点，分别搜索和该皇后同一列的位置//a[i]==y 表示 第i行的皇后存储在第y列的位置上，因为任意两个皇后不能在同一列，如果条件成立，返回false，第x行的皇后不能存储在第y列上 //i+a[i]==x+y 因为a[i]=k,是第i行皇后的列数，再加上行数i。如果i+k==x+y，则（x，y）位置与第i行的皇后处于同一斜对角线上 ，不成立 //i-a[i]==x-y 因为a[i]=k,是第i行皇后的列数，再减去行数i。如果i-k==x-y，则（x，y）位置与第i行的皇后处于同一反斜对角线上，不成立 {if(a[i]==y)return false;if(i+a[i]==x+y)return false;if(i-a[i]==x-y)return false; }return true;//如果前面条件全部不成立，则说明，第x行的皇后可存储在第y列上}
void dfs(int row)//从第1行开始遍历
{if(row==n+1)//因为row从1开始，所以当相等时候，说明找到第n个皇后，cnt表示有多少种皇后摆放方式，每次找到n个皇后，cnt+1 {cnt++;return;}for(int i=1;i<=n;i++)//这里i是列，对于每一行row的皇后，从左到右依次遍历 {if(check(row,i))//如果为真表示在第row行的皇后存储在第i列 {a[row]=i;//将列数存储在a数组中，记录 dfs(row+1);//进入深搜 a[row]=0;//退出dfs后，回溯还原 }}
}
int main()
{cin>>n;//输入n皇后个数 dfs(1);//从1开始 cout<<cnt;//输出n皇后摆放种数 return 0;
}输入8 得到结果92
再看一个例题
3.2AcWing 843 n-皇后问题
n−皇后问题是指将 n 个皇后放在 n×nn×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 nn，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤91≤n≤9
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
解题思路：顺序就是我们可以向全排列那样搜，因为每一行都有放一个皇后所以我们可以枚举每一行的皇后放在什么位置，这里我们需要注意剪枝，我们也可以先写一个全排列，然后在判断每个皇后的位置。
代码如下：
#include <iostream>
using namespace std;
const int N = 20; // bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径int n;
char g[N][N];
bool col[N], dg[N], udg[N];void dfs(int u) {// u == n 表示已经搜了n行，故输出这条路径if (u == n) {for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;puts(""); // 换行return;}// 枚举u这一行，搜索合法的列int x = u;for (int y = 0; y < n; y ++ )// 剪枝(对于不满足要求的点，不再继续往下搜索) if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {col[y] = dg[y - x + n] = udg[y + x] = true;g[x][y] = 'Q';dfs(x + 1);g[x][y] = '.'; // 恢复现场col[y] = dg[y - x + n] = udg[y + x] = false;}
}int main() {cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
} 重点解析：在斜对角线上的所有坐标 x-y 的值恒相等 ，设为常数字b1，在反斜对角线上的所有坐标 x+y 的值恒相等 ，设为常数字b2，分别用dg[] 和 udg[]两个bool数组表示，dg[b1]=false,表示在棋表中 y=x-b1 的斜对角线上的所有坐标尚未有皇后占领，若皇后在该y=x-b1斜线上出现过一次，则将dg[b1]=false更改为true，表示在y=x-b1斜对角线上位置已被占领，下次在判断条件时，判断到这个斜线y=x-b1对于的dg数组值为true时，就不满足判断条件 +n是因为数组有可能出现负数，加上n，能保证y - x + n的值恒大于等于0 ugb同理
col[],这个从0开始遍历到n-1列，皇后每一相同列只能出现一次
本博客是在观看b站 n皇后问题_哔哩哔哩_bilibili
基础上做笔记，如果有侵权，请联系作者，谢谢
