八皇后问题说明
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。文章来源:https://www.toymoban.com/news/detail-629039.html
思路分析
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列,然后判断是否OK,如果不OK,继续放在第二列、第三列,依次把所有列都放完,找到一个合适的位置
- 继续第三个皇后,还是第一列、第二列…直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
- 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到。
- 然后回头继续第一个皇后放第二列,后面继续循环 1,2,3,4 的步骤
代码实现如下
public class EightQueens {
private static final int N = 8; //棋盘大小为8x8
private static int[] queens = new int[N];// 一维数组表示每一行皇后所在的列数
private static int count = 0;
//编写一个 main 方法
public static void main(String[] args) {
solve(0); //从第 0 行开始放置皇后
System.out.println("最多有"+ count + "种排序");
}
//递归处理皇后在每行的位置并放到 queens数组中
private static void solve(int row){
if( row >= N ){ //所有行都放置好了皇后,找到一个解
print();
return;
}
for(int col = 0; col < N; col++){
if (isSafe(row, col)) { // 当前位置安全,可以放置皇后
queens[row] = col; // 在当前行,将皇后放在第col列
solve(row + 1); // 递归放置下一行的皇后
}
}
}
//判断是否在每一行、每一列、对角线
private static boolean isSafe(int row, int col) {
// 检查当前位置是否安全
for (int i = 0; i < row; i++) {
// 检查是否同一列或者同一对角线上已经存在皇后
if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
return false; // 不安全
}
}
return true; // 安全
}
//打印输出全部解
private static void print(){
count++;
for(int i = 0; i < N; i++){
System.out.print(queens[i] + " ");
}
System.out.println();
}
}
执行结果
文章来源地址https://www.toymoban.com/news/detail-629039.html
到了这里,关于Java实现八皇后问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!