[leetcode] 51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

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

示例 1：

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

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

解题方法

dfs

题目中说了每个皇后不能在同一行或同一列或同一斜线上，那么我们可以按行做dfs遍历。每次dfs遍历时，只需要检查当前列、当前的两个对角线是否已经放置过其他皇后。没有的话就可以在当前位置放置皇后，继续下一层dfs遍历。

顺着上面的思路，我们可以提供行数组col、列数组row、右上到左下的对角线数组dpos、左上到右下的对角线数组dneg，当棋子被放置在某个位置时，就可以将对应数组的位置置为1。这样我们每次dfs遍历时，只需要检查该棋子对应的数组位置是否被占用就可以了。

行数组col和列数组row位置比较好表示，但是右上到左下的对角线数组dpos和左上到右下的对角线数组dneg位置怎么表示呢？我们可以看如下图示。

我们可以给按图示箭头给不同的对角线标记不同的数组下标。设棋子在当前位置的行为i，列为j，棋盘大小是n×n。

• 先以右上到左下的对角线数组dpos为例，我们可以将i + j设置为数组下标。
• 再以左上到右下的对角线数组dneg为例，我们可以将i - j的值用来区分不同对角线的位置。由于i - j可能为负数，所以我们可以将i - j + n - 1作为数组下标，这样数组下标就会从0开始。

数组的表示方法也讲完了，那我们看下java代码吧。

java代码

public List<List<String>> solveNQueens(int n) {
    if (n == 0) {
        return new ArrayList<>();
    }
    // 以下数组记录行、列、对角线是否已被棋子占用
    // 行
    int[] row = new int[n];
    // 列
    int[] col = new int[n];
    // 右上到左下的对角线
    int[] dpos = new int[2 * n - 1];
    // 左上到右下的对角线
    int[] dneg = new int[2 * n - 1];
    List<List<String>> list = new ArrayList<List<String>>();
    dfs(list, row, col, dpos, dneg, n, 0);
    return list;

}

// index代表当前遍历深度，即棋盘行数
public void dfs(List<List<String>> list, int[] row, int[] col, int[] dpos, int[] dneg, int n, int index) {
    if (index == n) {
        List<String> list1 = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            StringBuilder bd = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (row[i] == j) {
                    bd.append('Q');
                } else {
                    bd.append('.');
                }
            }
            list1.add(bd.toString());
        }
        list.add(list1);
        return;
    }
    // i代表列
    for (int i = 0; i < n; i++) {
        // 检查该列和对角线是否已被前面放置的棋子占用
        if (col[i] == 1 || dpos[index + i] == 1 || dneg[index - i + n - 1] == 1) {
            continue;
        }
        // 这里需要注意，行数组存储棋子放置在哪一列
        row[index] = i;
        col[i] = 1;
        dpos[index + i] = 1;
        dneg[index - i + n - 1] = 1;
        dfs(list, row, col, dpos, dneg, n, index + 1);
        col[i] = 0;
        dpos[index + i] = 0;
        dneg[index - i + n - 1] = 0;
    }
}

复杂度分析

时间复杂度：$O(N^2)$，需要遍历整个n×n棋盘。
空间复杂度：$O(N)$，一是需要提供四个数组，二是dfs会遍历n层。

• 个人公众号
  
• 个人小游戏