算法の递归の八皇后问题 | Monster

算法の递归の八皇后问题

八皇后问题
  • 在国际西洋棋棋手马克思·贝瑟尔于1848年提出:在8*8格的国际象棋上拜访八个皇后,使其不能相互攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,求有多少种摆法
  • 思路:
    • 将第一个皇后放在第一行第一列
    • 第二个皇后放在第二行第一列,然后判断是否满足放置条件,如果不满足,往后依次放在第二列、第三列、把所有的列都放完,找到一个合适的
    • 继续第三个皇后,直到第八个皇后也能放在一个不冲突的位置,算是找到了一个正确解
    • 当得到一个正确解时,在栈回退到上一个栈时。就会开始回溯,即将第一个皇后放到第一列的所有正确解,全部得到
    • 然后回头继续将第一个皇后放置第二列,后面继续循环执行上述四步骤,即可得到所有解
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    /**
    * @author Monster
    * 八皇后问题
    */
    public class Queen8 {




    // 放置皇后位置可行解的数组
    int arr[] = new int[8];

    static int count = 0;

    public static void main(String[] args) {
    Queen8 queen = new Queen8();
    queen.placeQueen(0); // 开始放置皇后从第一个位置开始
    System.out.println(count); // 记录摆法的数量

    }

    // 放置第n个皇后 考虑到递归 需要传递次参数
    private void placeQueen(int n){
    if(n == 8){
    // TODO 此时表示已经放置完毕
    show();
    return;
    }

    // TODO 依次放入皇后并判断是否冲突
    for(int i = 0; i< 8; i++){
    // 先将当前皇后放入该行的第一列
    arr[n] = i;

    // 判断皇后放置到i列时 是否冲突
    if(judge(n)){
    // TODO 不冲突 继续往下一行放皇后 开始递归
    placeQueen(n+1);
    }
    }

    }


    // 判断是否冲突 当我们放置第n个皇后的时候。就去检测该皇后是否与之前的摆放位置冲突
    public boolean judge(int num){
    for (int i = 0; i < num ; i++) {
    // TODO arr[i] == arr[num] 表示在同一列 不满足放置条件
    // TODO Math.abs(num-i) == Math.abs(arr[num] - arr[i]) 判断是否在一条斜线上 这里通过斜率判断 平面直角坐标系中一条直线上的两个点斜率相同
    if(arr[i] == arr[num] || Math.abs(num-i) == Math.abs(arr[num] - arr[i])){
    return false;
    }
    }
    return true;
    }



    // 打印数组的方法
    private void show(){
    for (int i : arr) {
    System.out.print(i+" ");
    }
    count++;
    System.out.println();
    }


    }
-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%