史上最简明八皇后问题分析与套路总结

项目github地址：bitcarmanlee easy-algorithm-interview-and-practice 欢迎大家star，留言，一起学习进步

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。(问题描述来自参考文献1)

数学王子高斯当年花费了无数心血，最后计算认为八皇后问题有76种解法，现在我们通过计算机模拟可以轻松计算出八皇后问题的真正解法有92种。能让高斯栽跟头的问题，可想而知计算的复杂性与难度。

高斯将八皇后的解法推导出76种，已经算是非常厉害了。这不能怨高斯，而是八皇后的计算复杂度确实太高。 该问题的整体思路还是暴力解法 1.先列出所有可能的皇后摆放方式。 2.再检查该种摆放方式是否符合要求。

具体的执行过程如下： 先将第一个皇后放在第一行第一列，然后将第二个皇后放在第二行第一列，判断该种摆法是否符合要求。很明显这样摆不行，有两个皇后会在同一列。再将第二个皇后放在第二行第二列，这样也不行，两个皇后会在一条斜线上。将第二个皇后放在第二行第三列，这样满足当前条件。 目前已经有两个皇后满足条件，接下来放第三个，还是从第三行第一列开始放置，不满足条件再放第二列，第三列…一直到第8个皇后也能放在一个不冲突的位置，此时找到一个符合要求的解。 然后我们开始回溯，将第一个皇后放在第一行第二列，后面的就继续按上面的方式循环，一直到回溯完毕，找出所有符合条件的解为止。

参考文献2有张图，比较详细的用图描述了上面的过程，贴出来大家参考。下面图描述的是4皇后的回溯过程，原理跟8皇后是一致的。

上面原理分析完毕，接下来看代码实现。