八皇后问题的程序解答
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
由上面的概述可以得出, 任意两个皇后不能处于同一行,同一列, 或者同一斜线. 这条规则是校验八皇后是否合法的规则, 后面的代码将根据这条规则来编写.
1. 回溯法
首先我们定义一个数组 array = {0 , 4, 7, 5, 2, 6, 1, 3},用单数组表示八皇后的位置,
上面的数组依次表示8皇后在棋盘的位置, array [0] = 0, array [1]=4, array[index] = val ,可以得出每个八皇后的位置在第index+1行,
在(val+1) 列, 入下图所示, 可以看到下面的表格是满足任意两个皇后不能处于同一行,同一列, 或者同一斜线.
| 1 | |||||||
|---|---|---|---|---|---|---|---|
| 2 | |||||||
| 3 | |||||||
| 4 | |||||||
| 5 | |||||||
| 6 | |||||||
| 7 | |||||||
| 8 |
1.1 八皇后的规则校验
/**
* 校验该皇后是否和前面的皇后冲突
*
* @param index 第几个皇后(index表示在数组的索引)
* @return 该皇后的位置是否冲突
*/
public boolean isJudge(int index) {
if (index == 0) {
// 如果是在数组的第一个皇后直接返回不冲突
return true;
}
// 遍历该皇后前面的皇后
for (int i = 0; i < index; i++) {
// 1. 判断该皇后是否和前面的皇后在同一列
if (array[index] == array[i]) {
// 假如array[0] = 0, array[1]=1, array[2] = 1那么这个就是冲突的
return false;
}
// 2. 判断该皇后是否和其他的皇后在同一条斜线
// array = {0,1,2,3,4,5,6,7} , 这8个皇后在同一条斜线, 由此可以得到, 他们的差值相等的
// 第一个皇后在第一行第一列, 第二个皇后在第二行第二列, 第三个皇后在第三行第三列
// 由此可得第n个皇后和n-个皇后的位置(index)的差值,等于他们所在y轴(val)的差值
if (Math.abs(array[index] - array[i]) == Math.abs(index - i)) {
return false;
}
// 3. 判断是否在同一行由于我们已经规定好了 array = {0 , 4, 7, 5, 2, 6, 1, 3},
// 每一个皇后的位置的行在 array[index] =val, 由index 决定,所以肯定不在同一行
}
return true;
}
1.2 放入皇后
/**
* @param index 皇后在数组的位置(index)
*/
public void putQueue(int index) {
if (index == max) {
// 当index = max的时候, 表示皇后已经放了8个,
num++;
printQueue();
return;
}
for (int i = 0; i < max; i++) {
// 将皇后放入数组, 这里的i代表皇后在棋盘的列
array[index] = i;
if (isJudge(index)) {
// 不冲突, 继续放入皇后到数组
putQueue(index + 1);
}
// 冲突的话, 继续循环放入新的皇后到数组(改变当前皇后的列)
}
}
1.3 完整代码如下
public class Queue8Demo {
//定义一个max表示共有多少个皇后
int max = 8;
//定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
int[] array = new int[max];
// 解法计数器
static int num = 0;
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
Queue8Demo queue8 = new Queue8Demo();
queue8.putQueue(0);
System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
}
/**
* 校验该皇后是否和前面的皇后冲突
*
* @param index 第几个皇后(index表示在数组的索引)
* @return 该皇后的位置是否冲突
*/
public boolean isJudge(int index) {
if (index == 0) {
// 如果是在数组的第一个皇后直接返回不冲突
return true;
}
// 遍历该皇后前面的皇后
for (int i = 0; i < index; i++) {
// 1. 判断该皇后是否和前面的皇后在同一列
if (array[index] == array[i]) {
// 假如array[0] = 0, array[1]=1, array[2] = 1那么这个就是冲突的
return false;
}
// 2. 判断该皇后是否和其他的皇后在同一条斜线
// array = {0,1,2,3,4,5,6,7} , 这8个皇后在同一条斜线, 由此可以得到, 他们的差值相等的
// 第一个皇后在第一行第一列, 第二个皇后在第二行第二列, 第三个皇后在第三行第三列
// 由此可得第n个皇后和n-个皇后的位置(index)的差值,等于他们所在y轴(val)的差值
if (Math.abs(array[index] - array[i]) == Math.abs(index - i)) {
return false;
}
// 3. 判断是否在同一行由于我们已经规定好了 array = {0 , 4, 7, 5, 2, 6, 1, 3},
// 每一个皇后的位置的行在 array[index] =val, 由index 决定,所以肯定不在同一行
}
return true;
}
/**
* 放入皇后到数组
* @param index 皇后在数组的位置(index)
*/
public void putQueue(int index) {
if (index == max) {
// 当index = max的时候, 表示皇后已经放了8个,已经得到一种解法
num++;
printQueue();
return;
}
for (int i = 0; i < max; i++) {
// 将皇后放入数组, 这里的i代表皇后在棋盘的列
array[index] = i;
if (isJudge(index)) {
// 不冲突, 继续放入皇后到数组
putQueue(index + 1);
}
// 冲突的话, 继续循环放入新的皇后到数组(改变当前皇后的列)
}
}
public void printQueue() {
System.out.print("解法" + num + ":");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
}
System.out.println();
}
}
总结
- 通过递归解决了八皇后的解法, 学习递归的用法