数据结构和算法——递归-八皇后问题（回溯算法）
看完 数据结构与算法——递归-迷宫问题 后，我们对递归和回溯算法有了一个基本的认识，本篇将讲解 一个著名的问题：八皇后问题，能让我们对递归和回溯有一个更深刻的认识。
八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有 76 种方案。1854年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以解决此问题。
可以去百度搜索下这个小游戏，自己玩几下感受下，还是很难的
八皇后思路分析
用递归回溯算法找出八皇后有多少种摆法，其实就是暴力穷举，思路如下：
-
第一个皇后先放第一行第一列
-
第二个皇后放在第二行第一列，然后判断是否符合规则，如果不符合规则，则继续放在第 2 列，依次的测试下去，直到符合规则后，放第三个皇后。
-
继续第 3 个皇后，直到 8 个皇后都放到了棋盘上，并且没有违反规则，就算是一个解答
-
当得到一个正确解时，记录下棋盘上的皇后的所有坐标（在每一次放皇后符合规则后都会记录本坐标），方便我们打印查看结果，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解全部拿到
-
然后回头继续第一个皇后放第二列，后面继续循环执行前面 4 步，以此类推，当求完第一行的皇后在每个列上的所有答案，就是全部解了（一共92种）
如果这里读不明白，就继续往下看，结合后面的细节分析和代码注释 看懂代码，就好理解了。
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}，这个是存储结果，数组下标表示第几行，对应的值则为在那一列上摆放着
/**
* 八皇后问题：
*
* 规则：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，
* 即：任意 两个皇后 都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
*
*/
public class Queue8 {
// 共有多少个皇后
int max = 8;
/**
* 存放皇后位置的结果
*
* 下标：表示棋盘中的某一行
* 对应的值：表示在这一行上，该皇后摆放在哪一列
* 比如：array[0] = 1，表示在第 1 行的第 2 列上摆放了一个皇后
*
* 由于规则，一行只能有一个皇后，所以可以使用一维数组来代替二维数组的棋盘结果
*
*/
int[] array = new int[max];
int count = 0; // 统计有多少个结果
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0); // 从第 1 行开始放置
}
/**
* 放置第 n 个（行）皇后
*特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯
* @param n
*/
private void check(int n) {
// n = 8，那么表示放第 9 个皇后，8 个皇后已经放完了（n 从0开始计数的）
// 表示找到了一个正确的结果，打印这个结果，并返回
if (n == max) {
count++;
print();
return;
}
// 开始暴力对比，从该行的第一列开始尝试放置皇后，直到与前面所放置的不冲突
for (int i = 0; i < max; i++) {
// 在该行的第 i 列上放置一个皇后
array[n] = i;
// 检测与已经放置的是否冲突
if (judge(n)) {
// 如果不冲突，则表示该行的皇后放置没有问题
// 开始进入下一行的皇后放置
check(n + 1);
}
// 如果冲突，这里什么也不做
// 因为是从第一列开始放置，如果冲突，则尝试放置到第 2 列上，直到放置成功
}
}
/**
* 按游戏规则要求，判定要放置的这一个皇后，和前面已经摆放的位置是否冲突
*
* @param n 第 n 个皇后
* @return
*/
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
if (
/*
如果他们的摆放位置一样，说明是在同一列
注：图是从下往上看
x .......
x .......
*/
array[i] == array[n]
/*
检测是否是同一斜列
array[下标] = 值
下标: 代表的是第几行
值：代表的是第几列
注：图是从下往上看
. x . . . . . . n = 1,value = 1
x . . . . . . . i = 0,value = 0
Math.abs(n - i) = 1
Math.abs(array[n] - array[i]) = 1
. . x . . . . . n = 1,value = 2
. x . . . . . . i = 0,value = 1
Math.abs(n - i) = 1
Math.abs(array[n] - array[i]) = 1
注：这里运用了角的斜率问题，如果斜率为1，则角就是45°，所以两点在一斜列上。
想不明白可以画图看看，如果两点在一斜列上的话，就会组成一个正方形。很巧妙
*/
|| Math.abs(n - i) == Math.abs(array[n] - array[i])
) {
return false;
}
}
return true;
}
/**
* 打印皇后的位置
*/
private void print() {
System.out.printf("第 %02d 个结果 ：", count);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
/**
* 下面是对于判定是否是同行，同列、同一斜列的分步骤测试，比较好理解
*/
@Test
public void judgeTest() {
//注：图是从下往上看
/*
* . . . . . . . .
* x . . . . . . .
*/
Queue8 queue8 = new Queue8();
queue8.array[0] = 0;
//======== 放置第 1 个皇后
// 判断是否是同一列
/*
* x . . . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 0; // 从第一列开始放置
System.out.println("同一列，是否通过：" + queue8.judge(1));
/*
* . x . . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 1;
// 第一列不行，放置到第 2 列上
System.out.println("同一斜列，是否通过：" + queue8.judge(1));
/*
* . . x . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 2;
// 第 2 列不行，放置到第 3 列上,这个肯定是可以的
System.out.println("同一列或同一斜列，是否通过：" + queue8.judge(1));
//======== 放置第 3 个皇后
/*
* x . . . . . . . // 计划放到这里
* . . x . . . . .
* x . . . . . . .
*/
queue8.array[2] = 0;
// 与第一行的在同一列上了
System.out.println("同一列，是否通过：" + queue8.judge(2));
/*
* . x . . . . . . // 计划放到这里
* . . x . . . . .
* x . . . . . . .
*/
queue8.array[2] = 1;
// 第一列不行，放置到第 2 列
// 这里与第 2 行的同一斜列了，也是不行的
System.out.println("同一斜列，是否通过：" + queue8.judge(2));
}
}
输出结果如下
第 01 个结果 ：0 4 7 5 2 6 1 3
第 02 个结果 ：0 5 7 2 6 3 1 4
第 03 个结果 ：0 6 3 5 7 1 4 2
第 04 个结果 ：0 6 4 7 1 3 5 2
第 05 个结果 ：1 3 5 7 2 0 6 4
第 06 个结果 ：1 4 6 0 2 7 5 3
第 07 个结果 ：1 4 6 3 0 7 5 2
第 08 个结果 ：1 5 0 6 3 7 2 4
第 09 个结果 ：1 5 7 2 0 3 6 4
第 10 个结果 ：1 6 2 5 7 4 0 3
第 11 个结果 ：1 6 4 7 0 3 5 2
第 12 个结果 ：1 7 5 0 2 4 6 3
第 13 个结果 ：2 0 6 4 7 1 3 5
第 14 个结果 ：2 4 1 7 0 6 3 5
第 15 个结果 ：2 4 1 7 5 3 6 0
第 16 个结果 ：2 4 6 0 3 1 7 5
第 17 个结果 ：2 4 7 3 0 6 1 5
第 18 个结果 ：2 5 1 4 7 0 6 3
第 19 个结果 ：2 5 1 6 0 3 7 4
第 20 个结果 ：2 5 1 6 4 0 7 3
第 21 个结果 ：2 5 3 0 7 4 6 1
第 22 个结果 ：2 5 3 1 7 4 6 0
第 23 个结果 ：2 5 7 0 3 6 4 1
第 24 个结果 ：2 5 7 0 4 6 1 3
第 25 个结果 ：2 5 7 1 3 0 6 4
第 26 个结果 ：2 6 1 7 4 0 3 5
第 27 个结果 ：2 6 1 7 5 3 0 4
第 28 个结果 ：2 7 3 6 0 5 1 4
第 29 个结果 ：3 0 4 7 1 6 2 5
第 30 个结果 ：3 0 4 7 5 2 6 1
第 31 个结果 ：3 1 4 7 5 0 2 6
第 32 个结果 ：3 1 6 2 5 7 0 4
第 33 个结果 ：3 1 6 2 5 7 4 0
第 34 个结果 ：3 1 6 4 0 7 5 2
第 35 个结果 ：3 1 7 4 6 0 2 5
第 36 个结果 ：3 1 7 5 0 2 4 6
第 37 个结果 ：3 5 0 4 1 7 2 6
第 38 个结果 ：3 5 7 1 6 0 2 4
第 39 个结果 ：3 5 7 2 0 6 4 1
第 40 个结果 ：3 6 0 7 4 1 5 2
第 41 个结果 ：3 6 2 7 1 4 0 5
第 42 个结果 ：3 6 4 1 5 0 2 7
第 43 个结果 ：3 6 4 2 0 5 7 1
第 44 个结果 ：3 7 0 2 5 1 6 4
第 45 个结果 ：3 7 0 4 6 1 5 2
第 46 个结果 ：3 7 4 2 0 6 1 5
第 47 个结果 ：4 0 3 5 7 1 6 2
第 48 个结果 ：4 0 7 3 1 6 2 5
第 49 个结果 ：4 0 7 5 2 6 1 3
第 50 个结果 ：4 1 3 5 7 2 0 6
第 51 个结果 ：4 1 3 6 2 7 5 0
第 52 个结果 ：4 1 5 0 6 3 7 2
第 53 个结果 ：4 1 7 0 3 6 2 5
第 54 个结果 ：4 2 0 5 7 1 3 6
第 55 个结果 ：4 2 0 6 1 7 5 3
第 56 个结果 ：4 2 7 3 6 0 5 1
第 57 个结果 ：4 6 0 2 7 5 3 1
第 58 个结果 ：4 6 0 3 1 7 5 2
第 59 个结果 ：4 6 1 3 7 0 2 5
第 60 个结果 ：4 6 1 5 2 0 3 7
第 61 个结果 ：4 6 1 5 2 0 7 3
第 62 个结果 ：4 6 3 0 2 7 5 1
第 63 个结果 ：4 7 3 0 2 5 1 6
第 64 个结果 ：4 7 3 0 6 1 5 2
第 65 个结果 ：5 0 4 1 7 2 6 3
第 66 个结果 ：5 1 6 0 2 4 7 3
第 67 个结果 ：5 1 6 0 3 7 4 2
第 68 个结果 ：5 2 0 6 4 7 1 3
第 69 个结果 ：5 2 0 7 3 1 6 4
第 70 个结果 ：5 2 0 7 4 1 3 6
第 71 个结果 ：5 2 4 6 0 3 1 7
第 72 个结果 ：5 2 4 7 0 3 1 6
第 73 个结果 ：5 2 6 1 3 7 0 4
第 74 个结果 ：5 2 6 1 7 4 0 3
第 75 个结果 ：5 2 6 3 0 7 1 4
第 76 个结果 ：5 3 0 4 7 1 6 2
第 77 个结果 ：5 3 1 7 4 6 0 2
第 78 个结果 ：5 3 6 0 2 4 1 7
第 79 个结果 ：5 3 6 0 7 1 4 2
第 80 个结果 ：5 7 1 3 0 6 4 2
第 81 个结果 ：6 0 2 7 5 3 1 4
第 82 个结果 ：6 1 3 0 7 4 2 5
第 83 个结果 ：6 1 5 2 0 3 7 4
第 84 个结果 ：6 2 0 5 7 4 1 3
第 85 个结果 ：6 2 7 1 4 0 5 3
第 86 个结果 ：6 3 1 4 7 0 2 5
第 87 个结果 ：6 3 1 7 5 0 2 4
第 88 个结果 ：6 4 2 0 5 7 1 3
第 89 个结果 ：7 1 3 0 6 4 2 5
第 90 个结果 ：7 1 4 2 0 6 3 5
第 91 个结果 ：7 2 0 5 1 4 6 3
第 92 个结果 ：7 3 0 2 5 1 6 4
可以在百度找到 8皇后 这个游戏，随便选一两个数据测试正确性，如果你想全部测试我没意见，结果是对的，你开心就好。
细节分析
一定要理解它这个 回溯 机制，比如拿其中这两个来分析（依据上面代码）
第 06 个结果 ：1 4 6 0 2 7 5 3
第 07 个结果 ：1 4 6 3 0 7 5 2
- 从第 1 行，到最后的第 8 行，这时 n+1 进入到第 9 行，发现已经放完 8 个皇后了，拿到一个完整的结果，
- 就返回到第 8 行的那个
check()方法中的check(n+1)哪里，因为第 8 行放置结果是 3 是一个正确解，那么回到这里来的时候，就会尝试剩下没有测试的列，比如第 4 列 - 从结果来看，肯定不满足，就一直会尝试直到，第 8 行的 3 变成 7（从0开始计数），这个 check 方法尝试完了，都没有出一个结果，就自动退出这个方法
- 回到了第 7 行的第 5 列这个结果上，又继续尝试，像第 2 步和第 3 步那样
- 从结果上来看，直到回到了第 4 行上，将 0 变成了 3，才发现这个位置与之前的不冲突，然后往下，进入到第 5 个皇后的放置上，重复递归操作
- 依次类推
其实这里递归的原理就是穷举法一样的思想，挨个的尝试，直到把所有的可能都尝试完。就像手机密码忘了，你一个一个去尝试，暴力破解。
*有一个 细节需要知道，这里的 不同行、不同列、不同斜列，不要求非连续的，也就是说，即使不是连续的斜列也算
x . . . . . . .
. . . . . . . .
. . x . . . . .
这样不连续的斜列，也算是在一条斜线上。一定要明白这个规则，才能使用那个判定斜列的算法
小结
-
重点 1 ：判定是否在棋盘是符合规则：是否是同一列、同一行（同行实际上是不存在的，所以不用做判断）、同一斜列
这里使用一维数组，来保存二维数组中的点的位置，使用如下的算法，来检验这个规则，这里设置的很巧妙
/* 如果他们的摆放位置一样，说明是在同一列 注：图是从下往上看 x ....... x ....... */ array[i] == array[n] /* 检测是否是同一斜列 array[下标] = 值 下标: 代表的是第几行 值：代表的是第几列 注：图是从下往上看 . x . . . . . . n = 1,value = 1 x . . . . . . . i = 0,value = 0 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 . . x . . . . . n = 1,value = 2 . x . . . . . . i = 0,value = 1 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 注：这里运用了角的斜率问题，如果斜率为1，则角就是45°，所以两点在一斜列上。 想不明白可以画图看看，如果两点在一斜列上的话，就会组成一个正方形。很巧妙 */ || Math.abs(n - i) == Math.abs(array[n] - array[i]) -
重点 2：递归的回溯流程，一定要明白是怎么回溯的
版权声明：本文为ljz111原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。