项目github地址：bitcarmanlee easy-algorithm-interview-and-practice 欢迎大家star，留言，一起学习进步
1.什么是八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。(问题描述来自参考文献1)
数学王子高斯当年花费了无数心血，最后计算认为八皇后问题有76种解法，现在我们通过计算机模拟可以轻松计算出八皇后问题的真正解法有92种。能让高斯栽跟头的问题，可想而知计算的复杂性与难度。
2.解法分析
高斯将八皇后的解法推导出76种，已经算是非常厉害了。这不能怨高斯，而是八皇后的计算复杂度确实太高。 该问题的整体思路还是暴力解法 1.先列出所有可能的皇后摆放方式。 2.再检查该种摆放方式是否符合要求。
具体的执行过程如下： 先将第一个皇后放在第一行第一列，然后将第二个皇后放在第二行第一列，判断该种摆法是否符合要求。很明显这样摆不行，有两个皇后会在同一列。再将第二个皇后放在第二行第二列，这样也不行，两个皇后会在一条斜线上。将第二个皇后放在第二行第三列，这样满足当前条件。 目前已经有两个皇后满足条件，接下来放第三个，还是从第三行第一列开始放置，不满足条件再放第二列，第三列…一直到第8个皇后也能放在一个不冲突的位置，此时找到一个符合要求的解。 然后我们开始回溯，将第一个皇后放在第一行第二列，后面的就继续按上面的方式循环，一直到回溯完毕，找出所有符合条件的解为止。
参考文献2有张图，比较详细的用图描述了上面的过程，贴出来大家参考。下面图描述的是4皇后的回溯过程，原理跟8皇后是一致的。
3.代码实现
上面原理分析完毕，接下来看代码实现。
public class NQueueV2 {
public static int N = 4;
public static int[][] boards = new int[N][N];
public static int result = 0;
public static void putQueQue(int k) {
if (k == N) {
result++;
for(int row=0; row for(int col=0; col System.out.print(boards[row][col] + " "); } System.out.println(); } System.out.println(); } else { for(int i=0; i if (check(k, i)) { boards[k][i] = 1; putQueQue(k+1); boards[k][i] = 0; } } } } public static boolean check(int row, int column) { for(int i=0; i if (boards[i][column] == 1) { return false; } } for(int m=row-1, n=column-1; m>=0 && n >= 0; m--, n--) { if (boards[m][n] == 1) { return false; } } for(int m=row-1, n=column+1; m>=0 && n if (boards[m][n] == 1) { return false; } } return true; } public static void main(String[] args) { putQueQue(0); System.out.println("result is: " + result); } } 代码输出结果： 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 result is: 2 上面的代码，为了方便输出最后结果，模拟的是4皇后，8皇后只需要将N改为8即可。 board二维数组，模拟的是棋盘，初始状态均为0，表示该位置没有放置皇后。如果该位置设为1，表明该位置有皇后。 k表示放置的皇后个数。如果k==N，说明N个皇后都被放置完毕，此时得到一个有效解。 for(int row=0; row for(int col=0; col System.out.print(boards[row][col] + " "); } System.out.println(); } 该部分代码输出有效解的状态，数组为1的位置表示该位置放置了皇后。 else部分代码，i表示的是第i列，check(k, i)方法表示的是在(k, i)这个位置放置皇后是否合法 for(int i=0; i if (boards[i][column] == 1) { return false; } } 这部分代码，表示两个皇后不能放置在同一列。 for(int m=row-1, n=column-1; m>=0 && n >= 0; m--, n--) { if (boards[m][n] == 1) { return false; } } 这部分代码，表示该皇后的左斜线部分不能有皇后。 for(int m=row-1, n=column+1; m>=0 && n if (boards[m][n] == 1) { return false; } } 这部分代码，表示该皇后的右斜线部分不能有皇后。 如果该位置能放置皇后，则将棋盘中该位置置为1，接下来往下一行放皇后putQueQue(k+1)。同时，在回溯的时候，需要将该位置置为0。 4.套路总结 所以看上去很复杂的八皇后问题，对着图，再对着代码分析，是不是感觉没那么难了？ 本质还是经典回溯算法的使用，跟前面我们讲到的排列组合类似。当了解完整个过程以后，回溯的难度甚至比排列组合还小！ 史上最全排列组合算法详解以及套路总结一文搞定 参考文献 1.https://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98 2.https://juejin.cn/post/6844903798926753805