八皇后问题

发表于   |   更新于

概述

  • 什么是八皇后问题？
  • 八皇后问题的难点是什么？
  • 如何实现？-源码

背景

如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上

难点有哪些

递归回溯法

所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static boolean settleQueen(int r){
    if (r == row){ // 为最后一行设置Queen时返回true，因为这行的结果不会影响其他的行
        return true;
    }
    for (int index = 0; index < col; index++){ // 从第一列遍历到最后一列
        // 当前行元素都清零,为回溯做铺垫
        clearRow(r);
        if (check(r, index)){
            chess[r][index] = 1;
            if (settleQueen(r + 1)){// 递归,如果返回false则回溯
                return true;
            }
        }
    }
    return false;
}

如何判断某个格子的斜线上是否已经存在Queen

同一条斜线上的元素的索引的和相等,或者同一条斜线上的元素的索引的差相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static boolean check(int i, int j){
    int sum = i + j; // 同一条斜线上的元素的索引的和相等
    int sub = i - j; // 或者 同一条斜线上的元素的索引的差相等
    for (int m = sum >= row ? row - 1 : sum; m >= 0 && sum - m < col; m--){
         if (chess[m][sum - m] == 1){
             return false;
         }
    }
    for (int m = sub <= 0 ? 0 : sub; m < row && m - sub < row; m++){
         if (chess[m][m - sub] == 1){
             return false;
         }
    }
    for (int m = 0; m < row; m++){
         if (chess[m][j] == 1){
             return false;
         }
    }
    return true;
}

GitHub地址

源码地址

参考链接

https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653193309&idx=1&sn=dd68a60873bb360e02afde21acde7d3f&chksm=8c99f687bbee7f91049c253dd3193c9a60d6d98cd315b0140a8635b2d34933b54a19127921a9&mpshare=1&scene=23&srcid=0508U4Oiadttnnqx96Es30nZ%23rd

https://blog.csdn.net/friendan/article/details/8809089