八皇后问题

首先我们了解一下著名的八皇后问题

八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以编程解决此问题。

八皇后的解决思路

思路一：暴力法

  • 从棋盘64个方格中，选出任意8个格子摆放皇后，检查每一种可能性
  • 一共有 C8/64 中可能性(大约是 4.4 * 10^9种摆法)

思路二：优化暴力法

  • 显然每个皇后不可能再同一行
  • 所以共有 8 ^ 8(16777216)种摆法，检查每一种摆法是否合理

回溯法

  • 回溯 + 剪枝

这就引入了我们今天的主角回溯法

回溯法

回溯法 ：可以理解为，通过不同的岔路口来通往目的地(找到想要的结果)

  • 每一步检查都选择一条路出发，能进则进，不能进则返回上一步(回溯)，换一条路试试.
  • 树 / 图的深度优先搜索(DFS), 八皇后，走迷宫都是典型的回溯应用。

四皇后问题

在解决八皇后问题之前，我们先把问题规模减小，看看如何解决四皇后问题

以下为四皇后问题的推导过程

  • 从第一行(1,1)开始放入皇后
    • 当(1,1)放入皇后之后， 与(1,1) 同行同列同对角线的都不能再放置皇后
  • 继续放第二行，(2,1)(2,2)都不能放置皇后, (2,3)可放置皇后
    • 放入以后与 (2,3) 同行同列同对角线的位置不能放置皇后
  • 继续放置第三方， 我们发现第三行 每一条路都已走不通. (如图一)
    • 所以接下来，就是回溯
  • 回溯 重新放置第二行到 (2,4)
  • 继续放置 第三行(3,2)
  • 再继续放置第四行，发现第四行已走不通，所以再次回溯.
    • 因为 二，三行已没有其它路可走，所以回溯第一行
  • 回溯 将第一行放置 (1,2)
  • 继续放置第二行 (2,4)
  • 放置第三行 (3,1)
  • 放置第四行 (4,3)
    • 截止这一步，我们走通了一种可能性
  • 再继续放置 (1,3),(2,1),(3,4),(4,2)
    • 到这一步，我们又走通了一种可能性
  • (1,4)时，如图，依然走不通。
  • 所以最终我们的答案是，有两种可能性.

WechatIMG242

WechatIMG243

WechatIMG244

整体思路：

所以 回溯算法解决八皇后问题的总体思路:

  • 逐行摆放皇后
  • 摆放一行后，找下一行是否有可以摆放的位置
    • 如果有，则摆放，继续下一行
    • 如果没有，则回溯， 换一种可能的路继续走
  • 能走到最后一行，就是其中一种答案

代码如下；

 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
70
71
72
73
74
75
76

// 存储最终结果数组
    List<List<String>> lists;

    // 存放每一行皇后的列号
    int[] cols;
    
    // 一共有多少合理的解法
    private int ways;

    // 皇后的个数
    private int queenCnt;

    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return null;
        cols = new int[n];
        queenCnt = n;
        lists = new ArrayList<>();

        // 从di 0 行开始
        place(0);
        return lists;
    }

    // 从第row行，开始摆放皇后
    void place(int row){
        // 当 行数 == 皇后数时，说明已经走到最后 ways++
        // 并且 组装结果数组
        if (row == queenCnt){
            ways ++;
            show();
            return;
        }

        for (int col = 0; col < queenCnt; col++) {
            if (isValid(row,col)){
                cols[row] = col;
                // 继续下一行
                // 如果一直没有可以放置的位置， 则回溯
                place(row + 1);
            }
        }
    }

    private boolean isValid(int row, int col){
        for (int i = 0; i < row; i++) {
            // 当前列 已经有 相同的了
            if (cols[i] == col) {
                return false;
            }

            // 对角线 已经有 相同的了
            if (row - i == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }
    
    // 组装最终结果数组
    void show(){
        List<String> list = new ArrayList<>();
        for (int row = 0; row < queenCnt; row++) {
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < queenCnt; col++) {
                if (cols[row] == col){
                    // 皇后位置
                    sb.append("Q");
                }else {
                    // 非皇后位置
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        lists.add(list);
    }

LeetCode相关题目

截屏2020-06-15下午11.26.31

其中51 和 面试题08.12 重复， 52和其它两道题的区别，也只在于最终输出形式，基本一样。