八皇后问题概述与算法以及探讨如何才能成为下象棋高手和约束满足问题CSP

八皇后问题，是一个古老而著名的问题，是回溯算法（深度优先搜索算法的回退过程）的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；

如下图所示，因为主对角线只有14条下图红色箭头，从对角线也只有14条下图蓝色箭头，每一个格点都有唯一的（i,j）坐标确定，而且可以发现，对角线上的元素i+j=恒定值，所以正是利用这样的性质，数组b和数组c是一维数组即可。数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；

解决算法：就是穷举遍历搜索的方式，实际上就是利用深度优先搜索算法（因为是递归的算法，里面会牵扯到不满足条件就函数返回，即回溯，又名回溯算法）。

们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。

总结：其实这种解题思路就跟我们下象棋是一样的嘛，我们人不就是一种深度优先搜索的思路吗，心里面的思考是：先想着第一步，然后第二步，第三步，如果第三步走不了，就回退一下思路即改一下第二步，这时候发现第三步就可以成功走了（这里最大搜索步伐深度就跟你的脑容量有关了，如果每种方案能够搜索得越深，则说明这个人想得越远，更有远见思维），以此类推，从而可以搜索到多种可行方案（但是每种方案的输赢率都不一样），回归到现实动作，每种方案的第一步都是我们即将落棋的地方。那么其实走棋厉不厉害就看你大脑的递归深度搜索能力强不强了（这个需要结合你的经验，在多种可行步伐中选出一种最优的（这样就可以压缩搜索空间，才能下棋速度又快又好），然后继续深度遍历）。所以要想下棋厉害，大脑的脑容量越高（使得搜索深度可以更深，相当于计算机内存），实战经验越丰富和勤于思考（使得搜索空间压缩越大，相当于计算机优化的选择性深度搜索算法），思维越快（使得搜索速度越快，相当于计算机cpu主频），那么你就是一个下棋高手了，如果你是程序员，那么你的程序解决这个问题就又快又好了。

上述属于穷举类的算法，也是暴力求解算法，一定能得到最优解，但是因为问题的复杂性，可能搜索空间巨大，可能计算机算几个小时甚至几天才能算出来，所以是否还可以用一些近似求解算法可以得到近似最优解，但是却可以大大节省搜索时间，比如遗传算法，群蚁算法等等（关于这些算法具体了解，可以看我这篇文章，群蚁算法、遗传算法、模拟退火算法等通俗详解），有待大家去深入思考。

最后再提一下，这个八皇后问题属于约束满足问题，即涉及了约束条件，除此之外我们熟知的线性规划问题是和约束满足问题并列的，两者都涉及了约束条件，但是这两类问题的目标不一样。约束满足问题，一般用于求解满足约束问题的所有解，所以使用搜索算法比较好，而线性规划或者整数规划问题，一般用于找出满足某个条件的最优解，一般使用单纯形法（研究生工程优化这个课会讲这个）和分支定界法等。