算法题（102）：八皇后

审题：

本题需要我们找出n*n的棋盘中，满足题目中所有位置规则的排列的总数，以及前三个排列方式的具体位置

时间复杂度分析：数据量小于25，可以允许2^n的算法

思路：

方法一：dfs暴力搜索

由于每行只能有一个棋子，所以我们可以一行一行的进行棋子排放，排放的时候注意当前位置是否满足列，主对角线，副对角线的规则。

综上，进入更深的搜索只需要知道该棋子是在哪一行插入即可

判断列是否可以插入：用bool类型的col数组来判断，初始化为false，表示该索引的列没被插入

判断主/副对角线是否可以插入：

我们需要对棋盘的对角线满足的函数关系进行判断

首先我们先给棋盘建立二维平面坐标系，行为x，列为y。不过这里直接判断函数有点难看，所以我们将坐标系进行翻转，从而得到右边的图

这里是主对角线，我们发现x-y得到的值都是一个整数，我们可以考虑用这个整数作为索引来访问bool数组，若bool数组为false则表示主对角线没有棋子，允许排列。

注意：这里的值可能为负数，所以我们可以加一个偏移量来充当索引

这是副对角线，同理可得，我们使用x+y作为索引记录副对角线是否有棋子插入，由于这里的x+y不可能等于负数，所以不用加偏移量

解题：

（1）变量创建

这里的path是用来记录排列方式的。

主对角线的线数是2n+1,副对角线数是n，不过为了统一，我们都用2*N来当他们的容量。

！！！：由于我们使用的是时间复杂度极高的dfs所以这里要尽量减少使用vector，而是使用普通数组代替vector。因为vector有很多边界检查等额外开销，但是普通数组有很多编译器都对它做了优化。

（2）主函数

（3）dfs

首先我们写出结束语句：

当每一行都插入了数据时，我们将count++，表示排列方式又多了一种，然后根据counts的值判断是否为前三个解，若是则输出path的数据

然后是排列逻辑：

先判断行，列，主副对角线是否有棋子存在，若都没有则进行bool数组状态更新，以及path的插入，然后进入dfs搜索下一行

回溯时：将状态返回，删除path的该层数据

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷