想要精通算法和SQL的成长之路 - N皇后问题

前言

想要精通算法和SQL的成长之路 - 系列导航

一. N皇后问题

原题连接

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

• 输入：n = 4
• 输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
• 解释：如上图所示，4 皇后问题存在两个不同的解法。

N皇后问题，本质就是穷举法。而回溯法的本质就是穷举。我们只需要考虑好几点：

1. 皇后之间，不能同行、同列、同对角线。那么我们需要一个函数来专门的判断。
2. 我们从棋盘的第一行往下，开始每行的某一个位置塞一个皇后。因为皇后性质，塞了一个元素之后就可以直接看下一行。

那么接下来开始说代码的编写部分。首先，我们回溯法还是需要讲究它的一个模板：

1. 条件判断，满足条件则加入结果集。
2. 循环递归，当前层处理。
3. 处理完回溯。

伪代码就是：

if(满足条件){ 
   加入结果集;
   return;
}
for (选择当前的递归层的元素，一般通过函数传进来) {
    处理节点;
    backtracking(下一层递归); 
    回溯
}
1
2
3
4
5
6
7
8
9

1.1 是否满足皇后性质

这里我们写个函数isValid，判断当前节点的同行、同列、斜对角线是否存在皇后。不过值得注意的几点是：

• 对角线存在两条，但是我们该元素所在行的下面几行都是不用判别的。
• 每行插入一个皇后后，就递归下一行，因此同一行中不可能存在两个皇后，可以不用判别。

因为我们是自顶向下不断地给每层插入一个皇后的，因此我们只需要判断当前元素所在行的上半部分棋盘即可。 如图：（后面两个我是打了马赛克，代表没放皇后）

代码如下：

/**
 1. @param row 当前元素所在行
 2. @param col 当前元素所在列
 3. @param n   一共有多少行/列
 4. @return
 */
public boolean isValid(int row, int col, int n) {
    // 检查元素所在列是否有重复的皇后
    // 当前元素的下面几行都是没有遍历到的
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }
    // 检查左对角线（西北--东南），同样地只需要检查当前元素所在行的上半部分
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    // 检查右对角线（东北-西南），同样地只需要检查当前元素所在行的上半部分
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}
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

1.2 最终代码

因为题目用的是String来代表一个棋盘，很不方便，因此我们改为用二维数组来替代，并且代表一个棋盘。那么我们初始化的时候，就应该做到：

1. 棋盘大小是 N x N

2. 棋盘的每个格子都是 "."，

3. 再写一个二维数组转ArrayList的代码。

最后完整代码如下：

public class Test51 {
    List<List<String>> res = new ArrayList<>();
    char[][] board;

    public List<List<String>> solveNQueens(int n) {
        // 初始化我们的数组
        board = new char[n][n];
        // 初始化的时候，没有放皇后，每个格子应该都是 . 
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        backtrack(n, 0);
        return res;
    }

    public void backtrack(int n, int row) {
        // 如果遍历到最后一行，则符合结果
        if (n == row) {
            res.add(transListFromCharArray());
            return;
        }
        // 我们从上往下一层层遍历，无需进行双重遍历。一行只能有一个皇后
        for (int col = 0; col < n; col++) {
            // 判断当前位置是否满足N皇后特性
            if (isValid(row, col, n)) {
                // 在当前格子加一个皇后
                board[row][col] = 'Q';
                // 下一层递归
                backtrack(n, row + 1);
                // 回溯
                board[row][col] = '.';
            }
        }
    }

    /**
     * @param row 当前元素所在行
     * @param col 当前元素所在列
     * @param n   一共有多少行/列
     * @return
     */
    public boolean isValid(int row, int col, int n) {
        // 检查元素所在列是否有重复的皇后
        // 当前元素的下面几行都是没有遍历到的
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查左对角线（西北--东南），同样地只需要检查当前元素所在行的上半部分
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // 检查右对角线（东北-西南），同样地只需要检查当前元素所在行的上半部分
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    // char[][]数组转List
    public List<String> transListFromCharArray() {
        ArrayList<String> res = new ArrayList<>();
        for (char[] chars : board) {
            res.add(new String(chars));
        }
        return res;
    }
}
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