【深度优先搜索】20行代码解决8皇后问题

八皇后算法描述如下：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！

用dfs解决：
搜索策略如下：
从第0行开始，我们依次给每一行放置一个皇后，对于一个确定的行，我们只需要枚举放置的列即可，在确保不冲突的情况下，一直搜索下去
如何判断是否发生了冲突？
因为我们是逐行放置的，所以行内是不会冲突的。
对于列也很好处理，如果某列被占用了，只需要一个数组标记即可。
处理同一斜线：
处在同一斜线上的横纵坐标之和或者差为定值
解释： 斜率是+-1，所以对应直线方程为x+y=k，或者x-y=k

 
 我们可以用这一点来标记一条对角线是否被占用
我们用col【i】记录下标为i的列是否被占用
       用x1【i】记录横纵坐标和为i的位置是否被占用
       用x2【i】记录横纵坐标差为i-8的位置是否被占用
                           因为差可能是负数，所以我们对差整体加8防止数组越界

 
 
#in

【深度优先搜索】20行代码解决8皇后问题最先出现在Python成神之路。