问题描述：
N皇后问题是指在N*N的棋盘上要摆N个皇后， 要求：任何两个皇后不同行，不同列也不再同一条斜线上， 求给一个整数N，返回N皇后的摆法数。
N皇后问题涉及到回溯的思想。我们通常用递归解决，代码实现会比较简单。递归其实可以看作底层帮我们维护了一个自动push、pop的堆栈。网上也有很多N皇后的相关题解，这篇文章经过我的整理，保证你能看懂。
理解DFS的关键在于解决“当下该如何做”。至于“下一步如何做”则与当下是一样的。
因此，我们在递归的时候，只要关心第一步应该如何开始，以及最后一步何时结束，就能够写出DFS的基本模型。
初步认识DFS
为了方便无基础的读者阅读，顺带写上用DFS求1~n全排列的解法。
如果想直接看N皇后问题，可直接跳转
算法分析：
这里我们可以将全排列模拟成对n个纸条标上数字，所以需要一个长度为n的数组a[n]，再用一个数组book记录数字是否已经被使用。当某纸条标上数字i后，则book[i]=1。由于求全排列还需要取出数字重新组合，要重新赋值为0。
第一步：
我们关注的问题是：如何找出一种排列方式？
void dfs(int k)
{
if (k > n) //n个字条都被标记了
{
return; //找完第一种，结束尝试
}
for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字
{
if (!book[i]) //如果数字未使用
{
a[k] = i; //标上i
book[i] = 1;
}
}
}第二步：
我们将第一步的处理方法递推到后面的每一步。很容易想到，我们在一个函数中实现第一步，然后通过递归调用这个函数实现解决思路相同的下一步，直到应有的处理方案都试完，就可以结束。这就是DFS。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int n = 3;
int a[n], book[n + 1];
void dfs(int k)
{
if (k > n) //n个字条都被标记了
{
for (int i = 1; i <= n; i++)
printf("%d", a[i]);
printf("\n");
return; //结束第一次尝试
}
for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字
{
if (!book[i]) //如果数字未使用
{
a[k] = i; //标上i
book[i] = 1;
dfs(k + 1); //函数的递归调用（自己调用自己），继续标记第k+1纸条，直到n张纸条都标记完
book[i] = 0;
/**
* 这里之所以要置0，是因为在进入这个代码时，
* dfs一次调用完成，已经能得到了第一组排列方式
* 接下来会往前回退求新的排列方式
* 必须收回原有的标记才能继续做新的尝试
**/
}
}
}
int main()
{
dfs(1); //k表示现在要标记的是纸条k，从第一个开始
}
N皇后问题
下面我们依照上面的思路解决N皇后问题。首先给出DFS的基本模型，实现过程中会稍作调整。
start：
初始化数组
dfs(k){ 放置第k个皇后
if(判断边界){ 合法则开始尝试
for(i=1;i<=n;i++){
尝试每一种可能
dfs(k+1) 继续下一种尝试
回溯，恢复状态
}
}
else{ 放置位置超出棋盘
完成第一次递归，求解数+1
返回
}
}
end
算法分析：
普通DFS:
我们需要一个二维数组当作棋盘。
首先：如何放置第一种摆法？
核心思路是：对走过的每一行，判断当前列的位置是否可放置，然后遍历每一列，就得到第一种摆法。
然后从第一行开始试，尝试n次。这就是N皇后的DFS解法。
要判断当前位置的列和对角线是否能放置棋子，
就要对走过的每一行都检查。因此，我们需要这样一个函数
bool check(int row, int col)
{
/**由于要判断当前位置的列和对角线是否能放置
* 就要对走过的每一行都检查 **/
for (int i = 1; i <= row; i++)
{
if (g[i][col]) //对每一行检查当前列
return false;
}
for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--)
{
if (g[i][j]) //检查左上斜线
return false;
}
for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++)
{
if (g[i][j]) //检查右上斜线
return false;
}
return true;
}纯DFS完整代码为
#include <bits/stdc++.h>
using namespace std;
const int n = 8;
int ans = 0;
int g[n + 1][n + 1];
bool check(int row, int col)
{
/**由于要判断当前位置的列和对角线是否能放置
* 就要对走过的每一行都检查 **/
for (int i = 1; i <= row; i++)
{
if (g[i][col]) //对每一行检查当前列
return false;
}
for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--)
{
if (g[i][j]) //检查左上斜线
return false;
}
for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++)
{
if (g[i][j]) //检查右上斜线
return false;
}
return true;
}
void dfs(int k) //k表示第k行
{
if (k > n)
{
ans++;
return;
}
for (int col = 1; col <= n; col++)
{ //遍历k行的每一列
if (check(k, col)) //如果该位置可放置
{
g[k][col] = 1;
dfs(k + 1);
g[k][col] = 0;
}
}
}
int main()
{
dfs(1);
cout << ans;
}时间复杂度O(N!),空间复杂度(N^2),下面我们将开始优化。由于我这里只介绍N皇后的递归解法，下面提供的解法主要是在思路上有所改进。
重述一遍思路：对走过的每一行，判断当前列的位置是否可放置，然后遍历每一列，就得到第一种摆法。
由于在N皇后规则中，同行同列且同一斜线仅存在1个皇后，那我们能否不用二维数组模拟棋盘呢？
优化1.0:
其实，我们可以用一维数组分别表示列和对角线上的棋子状态，通过直线斜率判断两个棋子是否在同一斜线上。
由于在这个棋盘中，放置棋子处于同一斜线上的斜率k仅可取1和-1。我们以图上A(x1,y1)和B(x2,y2)两点为例 由直线方程两点式:
$\frac{x-x1}{x2-x1}$=$\frac{y-y1}{y2-y1}$
化简一般式：y = $\frac{y2-y1}{x2-x1}$(x-x1) ，其中，k= $\frac{y2-y1}{x2-x1}$ 。显然，当且仅当$| y2-y1 |$=$|x2-x1|$时，两个棋子位于同一斜线上。在对遍历每列时，当前行就是*y2，当前列就是x2**。
首先，我们将列的值存入以行为下标的数组里，就可以同时表达行与列的关系。核心代码为：
for (int x2 = 1; x2 <= n; x2++) //对当前行的每列遍历
{
g[y2] = x2;
if(check(y2))dfs(...) //列的值已经存在g[]里面，找到当前行能够放置的x2
}注意：g[]不再表示位置是否已放置，而是表示y2行在哪一列放置了皇后。
这样，我们压缩了棋盘数组的空间。只要对每列遍历，找到当前行能够放置的x2就可以了。
然后加上判断位置是否可放置皇后的函数，就能完成啦。
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
const int n = 8;
int ans = 0;
int g[n + 1];
//注意：g[]不再表示某位置是否已放置，而是表示某行在哪一列放置了皇后,简单的说就是下标为行y,值为x的数组
bool check(int y2)
{
for (int y1 = 1; y1 < y2; y1++)
{
if (g[y2] == g[y1] || y2 - y1 == abs(g[y2] - g[y1])) //y2-y1==|x2-x1| (y1<y2)
/**
* 1. 检查走过的行中有无同一列放置的皇后
2. 检查走过的行中有无同一斜线放置的皇后(通过斜率判断)
*/
return false;
}
return true;
}
void dfs(int y2) //y2表示纵坐标为y2，即y2行
{
if (y2 > n)
{
ans++;
return;
}
for (int x2 = 1; x2 <= n; x2++) //对每列遍历，找到当前能够放置的x2
{
g[y2] = x2;
if (check(y2))
{
dfs(y2 + 1); //由于一直在对列遍历，无需一次dfs调用完成后恢复数组
}
}
}
int main()
{
dfs(1);
cout << ans;
}优化1.1:
我们可以发现，只要知道行和列，对应的斜线位置也知道了。
于是，对前k行的每一列遍历时，只要判断该位置列和主对角线、副对角线能否放置就可以了。
由上图(转自leetcode)，我们将得出两个结论：
- 主对角线上，每个位置满足行下标与列下标之差相等
- 副对角线上，每个位置满足行下标与列下标之和相等
那么现在，我们y也可以用3个一维数组去维护棋盘的状态。它们分别表示列和主、副对角线。
这就是N皇后问题的常规DFS解法，我们的判断条件可以改为：
if (!(col[y] || line1[k + y] || line2[n-(k-y)])) //如果该位置可放置只需要对每列遍历一次，就可以判断该位置是否可放。
注意：由于对主对角线判断时会出现下标之差为负数，又因为对称性，同一棋盘会有两条主对角线行下标与列下标之差的绝对值相等。因此，这里判断的下标应该为n-(k-y) （有点像使数组下标溢出并作不进位处理）
核心代码如下：
void dfs(int k) //k表示第k行
{
if (k > n)
{
ans++;
return;
}
for (int y = 1; y <= n; y++)
{
if (!(col[y] || line1[k + y] || line2[n - (k-y)]))
{
col[y] = line1[k + y] = line2[n - (k-y)] = 1;
dfs(k + 1);
col[y] = line1[k + y] = line2[n - (k-y)] = 0;
}
}
}优化2:
完整代码如下
return [1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596][n-1]再见（逃 本文转自 https://blog.csdn.net/guanguandaren/article/details/115242535，如有侵权，请联系删除。
