问题描述
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！
八皇后问题
回溯
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法
思路分析
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适位置
- 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
代码实现
public class Queen8 {
private int max = 8; // 皇后个数
int[] array = new int[max]; // 存放皇后的数组 数组下标 表示 行 数组值表示列
private static int count = 0; // 统计
public static void main(String[] args) {
Queen8 queen8 = new Queen8();
queen8.check(0);
System.out.println("摆法一共有:" + count + "\t 种");
}
/**
* @param
* @return
* @description 放置皇后
**/
private void check(int n) {
if (n == max) {
print();
return;
}
for (int i = 0; i < max; i++) {
array[n] = i;
if (judge(n)) {
// 不冲突 继续放下一个皇后
check(n + 1);
}
// 如果冲突 接着循环下一列 继续判断
}
}
/**
* @param
* @return
* @description 判断是否冲突
**/
private boolean judge(int n) {
// 检测底 n 个之前放置的皇后是否冲突
for (int i = 0; i < n; i++) {
// 同行 || 同列 || 同斜线 则说明冲突 返回false ;
// array[i] == array[n] 数组值 表示列
// Math.abs(n-i) == Math.abs(array[n] - array [i]) 2个点的行差 == 列差 则2个点在同一斜线上
// 同一行 则不需要判断 n 表示行 在循环中是递增的 不会出现同行的情况
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
/**
* @param
* @return
* @description 打印
**/
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " \t");
}
System.out.println();
}
执行结果
0 4 7 5 2 6 1 3
.........
7 2 0 5 1 4 6 3
7 3 0 2 5 1 6 4
摆法一共有:92 种
