问题描述：
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。
第一步：
我们关注的问题是：如何找出一种排列方式？
1void dfs(int k) 2{ 3 if (k > n) //n个字条都被标记了 4 { 5 return; //找完第一种，结束尝试 6 } 7 for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字 8 { 9 if (!book[i]) //如果数字未使用 10 { 11 a[k] = i; //标上i 12 book[i] = 1; 13 } 14 } 15}
第二步：
我们将第一步的处理方法递推到后面的每一步。很容易想到，我们在一个函数中实现第一步，然后通过递归调用这个函数实现解决思路相同的下一步，直到应有的处理方案都试完，就可以结束。这就是DFS。
完整代码
1#include <bits/stdc++.h> 2using namespace std; 3const int n = 3; 4int a[n], book[n + 1]; 5void dfs(int k) 6{ 7 if (k > n) //n个字条都被标记了 8 { 9 for (int i = 1; i <= n; i++) 10 printf("%d", a[i]); 11 printf("\n"); 12 return; //结束第一次尝试 13 } 14 for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字 15 { 16 if (!book[i]) //如果数字未使用 17 { 18 a[k] = i; //标上i 19 book[i] = 1; 20 dfs(k + 1); //函数的递归调用（自己调用自己），继续标记第k+1纸条，直到n张纸条都标记完 21 book[i] = 0; 22 /** 23 * 这里之所以要置0，是因为在进入这个代码时， 24 * dfs一次调用完成，已经能得到了第一组排列方式 25 * 接下来会往前回退求新的排列方式 26 * 必须收回原有的标记才能继续做新的尝试 27 **/ 28 } 29 } 30} 31 32int main() 33{ 34 dfs(1); //k表示现在要标记的是纸条k，从第一个开始 35} 36
N皇后问题
下面我们依照上面的思路解决N皇后问题。首先给出DFS的基本模型，实现过程中会稍作调整。
1start： 2初始化数组 3dfs(k){ 放置第k个皇后 4 if(判断边界){ 合法则开始尝试 5 for(i=1;i<=n;i++){ 6 尝试每一种可能 7 dfs(k+1) 继续下一种尝试 8 回溯，恢复状态 9 } 10 } 11 else{ 放置位置超出棋盘 12 完成第一次递归，求解数+1 13 返回 14 } 15} 16end 17
算法分析：
普通DFS:
我们需要一个二维数组当作棋盘。
首先：如何放置第一种摆法？
核心思路是：对走过的每一行，判断当前列的位置是否可放置，然后遍历每一列，就得到第一种摆法。
然后从第一行开始试，尝试n次。这就是N皇后的DFS解法。
要判断当前位置的列和对角线是否能放置棋子，
就要对走过的每一行都检查。因此，我们需要这样一个函数
1bool check(int row, int col) 2{ 3 /**由于要判断当前位置的列和对角线是否能放置 4 * 就要对走过的每一行都检查 **/ 5 6 for (int i = 1; i <= row; i++) 7 { 8 if (g[i][col]) //对每一行检查当前列 9 return false; 10 } 11 for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--) 12 { 13 if (g[i][j]) //检查左上斜线 14 return false; 15 } 16 for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++) 17 { 18 if (g[i][j]) //检查右上斜线 19 return false; 20 } 21 return true; 22}
纯DFS完整代码为
1#include <bits/stdc++.h> 2using namespace std; 3const int n = 8; 4int ans = 0; 5int g[n + 1][n + 1]; 6bool check(int row, int col) 7{ 8 /**由于要判断当前位置的列和对角线是否能放置 9 * 就要对走过的每一行都检查 **/ 10 11 for (int i = 1; i <= row; i++) 12 { 13 if (g[i][col]) //对每一行检查当前列 14 return false; 15 } 16 for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--) 17 { 18 if (g[i][j]) //检查左上斜线 19 return false; 20 } 21 for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++) 22 { 23 if (g[i][j]) //检查右上斜线 24 return false; 25 } 26 return true; 27} 28void dfs(int k) //k表示第k行 29{ 30 if (k > n) 31 { 32 ans++; 33 return; 34 } 35 for (int col = 1; col <= n; col++) 36 { //遍历k行的每一列 37 if (check(k, col)) //如果该位置可放置 38 { 39 g[k][col] = 1; 40 dfs(k + 1); 41 g[k][col] = 0; 42 } 43 } 44} 45 46int main() 47{ 48 49 dfs(1); 50 cout << ans; 51}
时间复杂度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。
首先，我们将列的值存入以行为下标的数组里，就可以同时表达行与列的关系。核心代码为：
1 for (int x2 = 1; x2 <= n; x2++) //对当前行的每列遍历 2 { 3 g[y2] = x2; 4 if(check(y2))dfs(...) //列的值已经存在g[]里面，找到当前行能够放置的x2 5 }
注意：g[]不再表示位置是否已放置，而是表示y2行在哪一列放置了皇后。
这样，我们压缩了棋盘数组的空间。只要对每列遍历，找到当前行能够放置的x2就可以了。
然后加上判断位置是否可放置皇后的函数，就能完成啦。
完整代码如下：
1#include <bits/stdc++.h> 2using namespace std; 3const int n = 8; 4int ans = 0; 5int g[n + 1]; 6//注意：g[]不再表示某位置是否已放置，而是表示某行在哪一列放置了皇后,简单的说就是下标为行y,值为x的数组 7bool check(int y2) 8{ 9 for (int y1 = 1; y1 < y2; y1++) 10 { 11 if (g[y2] == g[y1] || y2 - y1 == abs(g[y2] - g[y1])) //y2-y1==|x2-x1| (y1<y2) 12 /** 13 * 1. 检查走过的行中有无同一列放置的皇后 14 2. 检查走过的行中有无同一斜线放置的皇后(通过斜率判断) 15 */ 16 return false; 17 } 18 return true; 19} 20void dfs(int y2) //y2表示纵坐标为y2，即y2行 21{ 22 if (y2 > n) 23 { 24 ans++; 25 return; 26 } 27 for (int x2 = 1; x2 <= n; x2++) //对每列遍历，找到当前能够放置的x2 28 { 29 g[y2] = x2; 30 if (check(y2)) 31 { 32 dfs(y2 + 1); //由于一直在对列遍历，无需一次dfs调用完成后恢复数组 33 } 34 } 35} 36 37int main() 38{ 39 40 dfs(1); 41 cout << ans; 42}
优化1.1:
我们可以发现，只要知道行和列，对应的斜线位置也知道了。
于是，对前k行的每一列遍历时，只要判断该位置列和主对角线、副对角线能否放置就可以了。
由上图(转自leetcode)，我们将得出两个结论：
- 主对角线上，每个位置满足行下标与列下标之差相等
- 副对角线上，每个位置满足行下标与列下标之和相等
那么现在，我们y也可以用3个一维数组去维护棋盘的状态。它们分别表示列和主、副对角线。
这就是N皇后问题的常规DFS解法，我们的判断条件可以改为：
if (!(col[y] || line1[k + y] || line2[n-(k-y)])) //如果该位置可放置
只需要对每列遍历一次，就可以判断该位置是否可放。
注意：由于对主对角线判断时会出现下标之差为负数，又因为对称性，同一棋盘会有两条主对角线行下标与列下标之差的绝对值相等。因此，这里判断的下标应该为n-(k-y) （有点像使数组下标溢出并作不进位处理）
核心代码如下：
1void dfs(int k) //k表示第k行 2{ 3 if (k > n) 4 { 5 ans++; 6 return; 7 } 8 for (int y = 1; y <= n; y++) 9 { 10 if (!(col[y] || line1[k + y] || line2[n - (k-y)])) 11 { 12 col[y] = line1[k + y] = line2[n - (k-y)] = 1; 13 dfs(k + 1); 14 col[y] = line1[k + y] = line2[n - (k-y)] = 0; 15 } 16 } 17}
优化2:
完整代码如下
1return [1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596][n-1]
再见（逃 本文转自 https://blog.csdn.net/guanguandaren/article/details/115242535，如有侵权，请联系删除。