【原】字节和爱奇艺面试原题，N皇后

数据结构和算法 2023-06-10 发布于上海

展开全文

这是LeetCode上的第51题，在评论区看到这样的两个评论

问题描述

来源：LeetCode第51题

难度：困难

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

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

回溯算法解决

前面我们刚讲过解数独-回溯算法解决，这题和数独都是使用回溯算法解决的，回溯算法就是不断尝试，关于回溯算法我们讲过很多，回溯算法有一个经典的模板，具体也可以看下450，什么叫回溯算法，一看就会，一写就废。这里我们就以n等于4为例来画个图看下

n等于4的时候实际上是有两种结果的，因为图画不下，这里只画出来一个结果。根据上面的图我们可以看到它其实就是一颗n叉树，我们来看下代码

public List<List<String>> solveNQueens(int n) {
    char[][] chess = new char[n][n];
    // 初始化棋盘
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            chess[i][j] = '.';
    List<List<String>> res = new ArrayList<>();
    // 回溯算法
    backtrack(res, chess, 0);
    return res;
}

private void backtrack(List<List<String>> res, char[][] chess, int row) {
    // 棋盘所有的行都遍历完了，说明找到一个可行的解，把它加入到集合res中
    if (row == chess.length) {
        res.add(construct(chess));
        return;
    }
    // 相当于一颗n叉树
    for (int col = 0; col < chess.length; col++) {
        // 判断当前位置是否可以放皇后
        if (valid(chess, row, col)) {
            // 如果在当前位置放皇后不发生攻击，就在当前位置放个皇后
            chess[row][col] = 'Q';
            // 递归，下一行
            backtrack(res, chess, row + 1);
            // 撤销选择
            chess[row][col] = '.';
        }
    }
}

//row表示第几行，col表示第几列
private boolean valid(char[][] chess, int row, int col) {
    //判断当前列有没有皇后,因为他是一行一行往下走的，
    //我们只需要检查走过的行数即可，通俗一点就是判断当前
    //坐标位置的上面有没有皇后
    for (int i = 0; i < row; i++) {
        if (chess[i][col] == 'Q') {
            return false;
        }
    }
    //判断当前坐标的右上角有没有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    //判断当前坐标的左上角有没有皇后
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

//把数组转为list
private List<String> construct(char[][] chess) {
    List<String> path = new ArrayList<>();
    for (int i = 0; i < chess.length; i++) {
        path.add(new String(chess[i]));
    }
    return path;
}