在某平台上看到一个八皇后问题，很好奇就稍微了解了一下，然后也研究了一下他的实现算法。
题目
八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
方法：回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
解题思路
由题干我们可以知道每一行最多只能有一个皇后，所以我们可以定义出这样的一个规则，现在第一行第一个位置放置一个皇后，然后遍历行，在行中进行列遍历，找到满足条件的，以此类推，假如在第四行就已经没有路可走那么回到第三行，重新进行选择一个位置再进行遍历。
具体思路参见：https://juejin.im/post/5accdb236fb9a028bb195562
解题步骤
1.确定不允许落子规则
- 同一列不能有皇后；
- 已经落子的行的左上角和右上角不能有皇后；
首先定义一个二维数组chessboard[row][col]，第一个维度是行第二个维度是列，注意不要带入坐标轴哦，行列表示跟坐标轴是相反的！
如图，假设蓝色三角就是第二行皇后放置的位置，我们需要计算在他左右斜上方以及当前列上方是否有皇后，代码如下：
public boolean isSatisfy(int row, int col) {
//检查列是否有皇后
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 1) {
return false;
}
}
//检查左上对角线是否有皇后
for (int m = row - 1, n = col - 1; m >= 0 && n >= 0; m--, n--) {
if (chessboard[m][n] == 1) {
return false;
}
}
//检查右上对角线是否有皇后
for (int m = row - 1, n = col + 1; m >= 0 && n < MAX; m--, n++) {
if (chessboard[m][n] == 1) {
return false;
}
}
return true;
}2.回溯递归
解决了判别问题我们就要进行整个算法的核心，回溯递归：
public void putQueen(int row) {
if (row >= MAX) {
printAnswer();
return;
}
for (int col = 0; col < MAX; col++) {
if (isSatisfy(row, col)) {
chessboard[row][col] = 1;
putQueen(row + 1);
chessboard[row][col] = 0;
}
}
}上面的代码也就几行看起来很简单，但是理解起来可能就不一定那么简单了！
先知道递归什么时候结束，八行八列都被遍历则循环结束。
首先从第0行第0列开始我们的第一次遍历，然后开始从第二行找到合适的位置，如果很巧找到了，进入第三行的列遍历，假设一切顺利的话我们输出了第一种解法，然后开始遍历第0行第1列，如果还是那么恰好以此类推输出结果。
但是往往天不遂人愿，走着走着路就没了，那么就需要回到上一层。
例子：假设row = 6 的时候，假如chessboard [6][0]放置了一个皇后(row=6,col=0)；
那么接下来执行putQueen(6+1)也就是第七行的遍历；
假如遍历第七行所有列都没法满足条件以进入第八行遍历，那么会执行chessboard[row][col] = 0; (row=6,col=0)，将无法进入下一行的皇后位置清除；
此时col自增为1，然后执行isSatisfy(row,col) （row=6,col=1）如果能放置的话，重复上边的动作，如果不能放置的话继续自增col，放置到第6行的下一列；
如果第六行每一列都没法得到解决方案，那么说明第五行的某一列（假设是0列）是死路，进行第五行第二列的尝试遍历。
如此层层递归，最终得到了所有的解决方案！
完整代码
/**
* @author chenly
* @create 2020-05-10 19:56
*/
public class Queen {
public static final int MAX = 8;
private int[][] chessboard = new int[8][8];
//解法的数量
private int count = 0;
public boolean isSatisfy(int row, int col) {
//检查列是否有皇后
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 1) {
return false;
}
}
//检查左上对角线是否有皇后
for (int m = row - 1, n = col - 1; m >= 0 && n >= 0; m--, n--) {
if (chessboard[m][n] == 1) {
return false;
}
}
//检查右上对角线是否有皇后
for (int m = row - 1, n = col + 1; m >= 0 && n < MAX; m--, n++) {
if (chessboard[m][n] == 1) {
return false;
}
}
return true;
}
public void putQueen(int row) {
if (row >= MAX) {
printAnswer();
return;
}
for (int col = 0; col < MAX; col++) {
if (isSatisfy(row, col)) {
chessboard[row][col] = 1;
putQueen(row + 1);
chessboard[row][col] = 0;
}
}
}
private void printAnswer() {
count++;
System.out.println("第 " + count + " 种解：");
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
System.out.print(chessboard[i][j] + " ");
}
System.out.println();
}
}
}public class Main {
public static void main(String[] args) {
Queen queen=new Queen();
queen.putQueen(0);
}
}参考：