11、数据结构和算法 - 实战：递归-八皇后问题
1.1 八皇后问题
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。大数学家高斯认为一共有76种摆法，1854年在柏林的象棋杂志上不同的作者发表了共计40种不同的见解，后来还有人利用图论的方法得出共有92种摆法。
如何解决八皇后问题？
使用递归回溯法，这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后…
1.2 JAVA实现摆放方式
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
package com.yuanxw.datastructure.chapter11;
/**
* 8皇后问题
* 解：8皇后问题回溯方式
*/
public class Queen8Example {
// 最大步骤
private static int MAX_QUEEN = 8;
private static int playCount = 0;
private static int validCount = 0;
/**
* 棋局
* 下标(index)表示行
* 值(value)表示列
*/
private int chessGame[] = new int[MAX_QUEEN];
public static void main(String[] args) {
Queen8Example queen = new Queen8Example();
queen.play(0);
System.out.println(String.format("摆放8皇后游戏位置共【%s】种解法", playCount));
System.out.println(String.format("摆放8皇后游戏需要验证是否已经皇后冲突存在【%s】次", validCount));
}
/**
* 开始游戏
*/
public void play(int n) {
// 先退出条件：如果是最大的皇后，说明运行结束。
if (n == MAX_QUEEN) {
print();
playCount++;
return;
}
for (int i = 0; i < MAX_QUEEN; i++) {
// 把当前皇后n，放该行的第i列
chessGame[n] = i;
// 如果当前符合皇后的摆放规则，接着摆放下一行。
if (isValid(n)) {
// 递归摆放下一个皇后
play(n + 1);
}
}
}
/**
* 判断当前皇后所在的位置是否符合规则
* 判断说明
1.判断是否是在同一列：chessGame[i] == chessGame[n]
2.公式：Math.abs(n - i) == Math.abs(chessGame[n] - chessGame[i])
x,y[y-x](x-y)
0,0[0](0) 0,1[1](-1) 0,2[2](-2) 0,3[3](-3) 0,4[4](-4) 0,5[5](-5) 0,6[6](-6) 0,7[7](-7)
1,0[-1](1) 1,1[0](0) 1,2[1](-1) 1,3[2](-2) 1,4[3](-3) 1,5[4](-4) 1,6[5](-5) 1,7[6](-6)
2,0[-2](2) 2,1[-1](1) 2,2[0](0) 2,3[1](-1) 2,4[2](-2) 2,5[3](-3) 2,6[4](-4) 2,7[5](-5)
3,0[-3](3) 3,1[-2](2) 3,2[-1](1) 3,3[0](0) 3,4[1](-1) 3,5[2](-2) 3,6[3](-3) 3,7[4](-4)
4,0[-4](4) 4,1[-3](3) 4,2[-2](2) 4,3[-1](1) 4,4[0](0) 4,5[1](-1) 4,6[2](-2) 4,7[3](-3)
5,0[-5](5) 5,1[-4](4) 5,2[-3](3) 5,3[-2](2) 5,4[-1](1) 5,5[0](0) 5,6[1](-1) 5,7[2](-2)
6,0[-6](6) 6,1[-5](5) 6,2[-4](4) 6,3[-3](3) 6,4[-2](2) 6,5[-1](1) 6,6[0](0) 6,7[1](-1)
7,0[-7](7) 7,1[-6](6) 7,2[-5](5) 7,3[-4](4) 7,4[-3](3) 7,5[-2](2) 7,6[-1](1) 7,7[0](0)
* @param n
* @return
*/
public boolean isValid(int n) {
validCount ++;
for (int i = 0; i < n; i++) {
if (chessGame[i] == chessGame[n] || Math.abs(n - i) == Math.abs(chessGame[n] - chessGame[i])) {
return false;
}
}
return true;
}
/**
* 打印8皇后问题结果
*/
private void print() {
for (int i : chessGame) {
System.out.print((i + 1) + "\t");
}
System.out.println("");
}
}
执行结果：
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3
1 7 5 8 2 4 6 3
2 4 6 8 3 1 7 5
2 5 7 1 3 8 6 4
2 5 7 4 1 8 6 3
2 6 1 7 4 8 3 5
2 6 8 3 1 4 7 5
2 7 3 6 8 5 1 4
2 7 5 8 1 4 6 3
2 8 6 1 3 5 7 4
3 1 7 5 8 2 4 6
3 5 2 8 1 7 4 6
3 5 2 8 6 4 7 1
3 5 7 1 4 2 8 6
3 5 8 4 1 7 2 6
3 6 2 5 8 1 7 4
3 6 2 7 1 4 8 5
3 6 2 7 5 1 8 4
3 6 4 1 8 5 7 2
3 6 4 2 8 5 7 1
3 6 8 1 4 7 5 2
3 6 8 1 5 7 2 4
3 6 8 2 4 1 7 5
3 7 2 8 5 1 4 6
3 7 2 8 6 4 1 5
3 8 4 7 1 6 2 5
4 1 5 8 2 7 3 6
4 1 5 8 6 3 7 2
4 2 5 8 6 1 3 7
4 2 7 3 6 8 1 5
4 2 7 3 6 8 5 1
4 2 7 5 1 8 6 3
4 2 8 5 7 1 3 6
4 2 8 6 1 3 5 7
4 6 1 5 2 8 3 7
4 6 8 2 7 1 3 5
4 6 8 3 1 7 5 2
4 7 1 8 5 2 6 3
4 7 3 8 2 5 1 6
4 7 5 2 6 1 3 8
4 7 5 3 1 6 8 2
4 8 1 3 6 2 7 5
4 8 1 5 7 2 6 3
4 8 5 3 1 7 2 6
5 1 4 6 8 2 7 3
5 1 8 4 2 7 3 6
5 1 8 6 3 7 2 4
5 2 4 6 8 3 1 7
5 2 4 7 3 8 6 1
5 2 6 1 7 4 8 3
5 2 8 1 4 7 3 6
5 3 1 6 8 2 4 7
5 3 1 7 2 8 6 4
5 3 8 4 7 1 6 2
5 7 1 3 8 6 4 2
5 7 1 4 2 8 6 3
5 7 2 4 8 1 3 6
5 7 2 6 3 1 4 8
5 7 2 6 3 1 8 4
5 7 4 1 3 8 6 2
5 8 4 1 3 6 2 7
5 8 4 1 7 2 6 3
6 1 5 2 8 3 7 4
6 2 7 1 3 5 8 4
6 2 7 1 4 8 5 3
6 3 1 7 5 8 2 4
6 3 1 8 4 2 7 5
6 3 1 8 5 2 4 7
6 3 5 7 1 4 2 8
6 3 5 8 1 4 2 7
6 3 7 2 4 8 1 5
6 3 7 2 8 5 1 4
6 3 7 4 1 8 2 5
6 4 1 5 8 2 7 3
6 4 2 8 5 7 1 3
6 4 7 1 3 5 2 8
6 4 7 1 8 2 5 3
6 8 2 4 1 7 5 3
7 1 3 8 6 4 2 5
7 2 4 1 8 5 3 6
7 2 6 3 1 4 8 5
7 3 1 6 8 5 2 4
7 3 8 2 5 1 6 4
7 4 2 5 8 1 3 6
7 4 2 8 6 1 3 5
7 5 3 1 6 8 2 4
8 2 4 1 7 5 3 6
8 2 5 3 1 7 4 6
8 3 1 6 2 5 7 4
8 4 1 3 6 2 7 5
摆放8皇后游戏位置共【92】种解法
摆放8皇后游戏需要验证是否已经皇后冲突存在【15720】次