算法_递归_回溯_八皇后问题-蒲公英云

算法_递归_回溯_八皇后问题

小咪咪 2023-07-10 14:10 54阅读 0赞

文章目录

- 问题描述
- 思路
- 代码实现
- - 定义属性
  - 辅助方法：打印结果
  - 辅助方法：判断第n个皇后与之前是否冲突
  - 递归回溯
  - Test
  - Result

问题描述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路

第1个皇后先放第1行第1列
第2个皇后放在第2行第1列、然后判断是否OK[即判断是冲突]，如果不OK，继续放在第2列、第3列、依次把所有列都放完，找到一个合适
继续第3个皇后，还是第1列、第2列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第1个皇后，放到第1列的所有正确解，全部得到.
然后回头继续第1个皇后放第2列，后面继续循环执行 1,2,3,4的步骤

代码实现

定义属性

public class Queen8 {
    //皇后个数
    int max = 8;
    //皇后位置数组，索引表示行数，value表示列数
    int[] positons = new int[max];
    //结果总数
    int count;
    //判断总次数
    int judgeCount;
}

辅助方法：打印结果

/**
 * 打印结果
 */
private void print() {
    for (int i : positons) {
        System.out.print(i + " ");
    }
    System.out.println();
}

辅助方法：判断第n个皇后与之前是否冲突

/**
* 判断第n个皇后与之前是否冲突
 * @param n
 * @return
 */
private boolean judge(int n) {
    judgeCount++;
    for (int i = 0; i < n; i++) {
        if (positons[i] == positons[n] || n - i == Math.abs(positons[n] - positons[i])) {
            return false;
        }
    }
    return true;
}

递归回溯

/**
 * 递归回溯
 * @param n
 */
private void put(int n) {
    if (n == max) {
        print();
        count++;
        return;
    }
    for (int i = 0; i < max; i++) {
        positons[n] = i;
        if (judge(n)) {
            put(n + 1);
        }
    }
}

Test

public static void main(String[] args) {
    Queen8 queen8 = new Queen8();
    queen8.put(0);
    System.out.println("共有解法：" + queen8.count);
    System.out.println("尝试判断次数：" + queen8.judgeCount);
}

Result

0 4 7 5 2 6 1 3
0 5 7 2 6 3 1 4
0 6 3 5 7 1 4 2
0 6 4 7 1 3 5 2
1 3 5 7 2 0 6 4
1 4 6 0 2 7 5 3
1 4 6 3 0 7 5 2
1 5 0 6 3 7 2 4
1 5 7 2 0 3 6 4
1 6 2 5 7 4 0 3
1 6 4 7 0 3 5 2
1 7 5 0 2 4 6 3
2 0 6 4 7 1 3 5
2 4 1 7 0 6 3 5
2 4 1 7 5 3 6 0
2 4 6 0 3 1 7 5
2 4 7 3 0 6 1 5
2 5 1 4 7 0 6 3
2 5 1 6 0 3 7 4
2 5 1 6 4 0 7 3
2 5 3 0 7 4 6 1
2 5 3 1 7 4 6 0
2 5 7 0 3 6 4 1
2 5 7 0 4 6 1 3
2 5 7 1 3 0 6 4
2 6 1 7 4 0 3 5
2 6 1 7 5 3 0 4
2 7 3 6 0 5 1 4
3 0 4 7 1 6 2 5
3 0 4 7 5 2 6 1
3 1 4 7 5 0 2 6
3 1 6 2 5 7 0 4
3 1 6 2 5 7 4 0
3 1 6 4 0 7 5 2
3 1 7 4 6 0 2 5
3 1 7 5 0 2 4 6
3 5 0 4 1 7 2 6
3 5 7 1 6 0 2 4
3 5 7 2 0 6 4 1
3 6 0 7 4 1 5 2
3 6 2 7 1 4 0 5
3 6 4 1 5 0 2 7
3 6 4 2 0 5 7 1
3 7 0 2 5 1 6 4
3 7 0 4 6 1 5 2
3 7 4 2 0 6 1 5
4 0 3 5 7 1 6 2
4 0 7 3 1 6 2 5
4 0 7 5 2 6 1 3
4 1 3 5 7 2 0 6
4 1 3 6 2 7 5 0
4 1 5 0 6 3 7 2
4 1 7 0 3 6 2 5
4 2 0 5 7 1 3 6
4 2 0 6 1 7 5 3
4 2 7 3 6 0 5 1
4 6 0 2 7 5 3 1
4 6 0 3 1 7 5 2
4 6 1 3 7 0 2 5
4 6 1 5 2 0 3 7
4 6 1 5 2 0 7 3
4 6 3 0 2 7 5 1
4 7 3 0 2 5 1 6
4 7 3 0 6 1 5 2
5 0 4 1 7 2 6 3
5 1 6 0 2 4 7 3
5 1 6 0 3 7 4 2
5 2 0 6 4 7 1 3
5 2 0 7 3 1 6 4
5 2 0 7 4 1 3 6
5 2 4 6 0 3 1 7
5 2 4 7 0 3 1 6
5 2 6 1 3 7 0 4
5 2 6 1 7 4 0 3
5 2 6 3 0 7 1 4
5 3 0 4 7 1 6 2
5 3 1 7 4 6 0 2
5 3 6 0 2 4 1 7
5 3 6 0 7 1 4 2
5 7 1 3 0 6 4 2
6 0 2 7 5 3 1 4
6 1 3 0 7 4 2 5
6 1 5 2 0 3 7 4
6 2 0 5 7 4 1 3
6 2 7 1 4 0 5 3
6 3 1 4 7 0 2 5
6 3 1 7 5 0 2 4
6 4 2 0 5 7 1 3
7 1 3 0 6 4 2 5
7 1 4 2 0 6 3 5
7 2 0 5 1 4 6 3
7 3 0 2 5 1 6 4
共有解法：92
尝试判断次数：15720