n皇后问题图解_dfs算法的时间复杂度

非常经典的一道题：

N皇后问题： 
国际象棋中皇后的势力范围覆盖其所在的行、列以及两条对角线，现在考察如下问题：如何在n x n的棋盘上放置n个皇后，使得她们彼此互不攻击 。

免去麻烦我们这里假定n不是很大。。

（图片来自百度百科（这是8皇后问题的一种解法））

某leetcode大犇曾说过：“这个问题和解数独题目有一个很大的共同点，那就是：我都不会。”

好了下面开始分析：（废话警告）

初步判断这问题的特点有：

1.有个场地来放置单位。

2.各个单位之间有制约。

3.没有特殊的数学方法，得把某一个摆法摆出来才能判断是否可行。

于是萌新一般都会这么想：对于1,：我搞个二维数组来存。对于2：我搞个判定函数来一个一个判定。对于3：我暴力枚举。

那么算法框架大概就是：我对二维数组的所有情况进行枚举，然后对每种情况进行判定

over ，输个数字n，按下回车，双手离开键盘，等了老半天发现命令提示符只有个光标在跳动 |

如果是在做网题，说不定就判定是超时或者内存溢出，过不了。

然后就开始思考怎么优化：

对于1，我可以缩减吗····，改成一维数组，，，似乎徒增麻烦。

对于2，我可以有更巧妙的判断方法吗？·············有个鬼，还不得把每个棋子的每一行每一列每两个斜线都瞅一下。

对于3，我一定要把所有情况都举出来嘛？···(于是脑子里面开始摆起了棋子,模拟算法过程)

然后就会发现  比如第一行前两个格子一开始就摆了两个相邻的棋子，诶这不明摆着皇后互怼了吗！后面还继续枚举就太傻了吧···

这种傻事情做了不是白白增加耗时吗！

所以就思考如何在这种“傻情况”出现的时候就pass掉后面所有情况。。。

于是脑子陷入了一团乱麻。。。

打住！

咱们换个思考方式，既然直接想有点困难，不如我们想办法先做点处理，让这些玩意儿便于我们把弄。

再回头想想规则，皇后可以吃掉所处的一行一列以及斜线上的棋子，那也就是说，每一行都最多只能有一个棋子，每一列都最多只能有一个棋子，

那我们不妨把每一行看成一组！

那么这一组就只有n个可能性（一行n个位置 每一次只有一个位置被占用）

也就是单个一行有n种可能性

因为有n行

哈哈那么就瞬间只需要讨论n*n种可能性了！

 还记得我们之前的思考吗？：

对于3，我一定要把所有情况都举出来嘛？···(于是脑子里面开始摆起了棋子,模拟算法过程) 然后就会发现 比如第一行前两个格子一开始就摆了两个相邻的棋子，诶这不明摆着皇后互怼了吗！后面还继续枚举就太傻了吧··· 　　　这种傻事情做了不是白白增加耗时吗！ 　　　所以就思考如何在这种“傻情况”出现的时候就pass掉后面所有情况。。。

像这种情况：

（我的天这皇后画的…）

显然下面3,4,5····行都不用枚举了，直接pass掉

于是我们思路慢慢清晰了起来：

我们从第一行开始枚举，第一行第一格：

然后枚举第二行，也从第一格开始：

 判定一下，哇，不行，咋办呢？这情况下面所有行都没有枚举的必要了，但是本行还是可以继续的。。。于是我们开始枚举第二行第二个情况：

不行（斜线上互吃）。

继续第二行下一个情况：

行嘞！

那么我们就可以开第三行了：

不行（一列上吃）。

不行（斜线上吃）

 不行。

 还不行

 行嘞！

··················

好了，算法思路大概就出来了。

 我们就这样干下去，直到最后一行可行，那么我们就获得了一个可行解了，

然后我们想继续获得其他解，那么继续枚举下去，但是要退一步：

先从倒数第一行开始，我们枚举下一个，有解则输出，无解则继续。

倒数第一行结束了，咋办？

别忘了倒数第二行的情况还不一定枚举完了呢。

于是退到倒数第二行，继续如上操作。

··················

 干说着没用，撸代码：

#include<iostream> using namespace std; int main() { return 0; }

先准备好需要用的存储（这里用64个绰绰有余）

ans是用来存每一次的解 ans[1]表示第一行的那个元素的所在列的位置

#include<iostream> using namespace std; bool colMark[64] = { 0 };//元素所在列 如果有了元素在第k列 那么colMark[k]就标记上true bool naMark[64] = { 0 };//捺，撇···顾名思义，表示元素所在的两个斜线o.o 原理同上 bool pieMark[64] = { 0 }; int total = 0; //解的总个数 int N = 0; int ans[64] = { 0 }; int main() { return 0; }

然后下面先写一个显示函数： 

void showOneSolution()//用来显示一个解 { total++; for (int i = 1; i<=N; ++i) { cout << ans[i] << " "; } cout << endl; }

下面是核心：

void Dfs(int i) //可以百度学习 深度优先搜索 { if (i > N) //判断是否已经枚举完了N行 { showOneSolution(); //枚举完了就输出（此刻我们处于N+1行） return; //返回到第N行 } for (int j = 1; j <= N; ++j) //这里的j表示 本行的第j列 { if ((!colMark[j])&&(!naMark[j-i+N])&&(!pieMark[i+j])) //这里的"j-i+N" "i+j"建议自己体会 {　　　　　　　　　　//判断这个格子所在的两个斜线和所在列是否为空 colMark[j] = true; naMark[j - i + N] = true; pieMark[i + j] = true; ans[i] = j; Dfs(i + 1); colMark[j] = false; //这个格子枚举完了要进入本行第j+1个格子（或者结束本行） 走之前别忘了恢复标记 naMark[j - i + N] = false; pieMark[i + j] = false; } } }

 最后组装起来：（当然啦，还是建议自己撸代码，你会发现很多意想不到的问题~解决问题的同时也是进步）

#include<iostream> using namespace std; bool colMark[64] = { 0 }; bool naMark[64] = { 0 }; bool pieMark[64] = { 0 }; int total = 0; int N = 0; int ans[64] = { 0 }; void showOneSolution()//用来显示一个解 { total++; for (int i = 1; i<=N; ++i) { cout << ans[i] << " "; } cout << endl; } void Dfs(int i) { if (i > N) //判断是否已经枚举完了N行 { showOneSolution(); //枚举完了就输出（此刻我们处于N+1行） return; //返回到第N行 } for (int j = 1; j <= N; ++j) //这里的j表示 本行的第j列 { if ((!colMark[j]) && (!naMark[j - i + N]) && (!pieMark[i + j])) {　　　　　　　　　　//判断这个格子所在的两个斜线和所在列是否为空 colMark[j] = true; naMark[j - i + N] = true; pieMark[i + j] = true; ans[i] = j; Dfs(i + 1); colMark[j] = false; // 走之前别忘了恢复标记 naMark[j - i + N] = false; pieMark[i + j] = false; } } } int main() { cin >> N; Dfs(1); cout << total; system("pause"); return 0; }

总结：

思路混乱不妨换个角度理一理。

在纸上面画一画算法过程会有不少帮助。

代码少出错还是得多撸。

想什么呢？！撸代码！

今天的文章
n皇后问题图解_dfs算法的时间复杂度分享到此就结束了，感谢您的阅读。