leetcode 51. N-Queens N 皇后 (困难)

作者：okokabcd

2022 年 6 月 06 日
本文字数：2168 字
阅读完需：约 7 分钟

一、题目大意

标签: 搜索

https://leetcode.cn/problems/n-queens

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

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

二、解题思路

经典的递归入门题目，在 N*N 的棋盘上面放上 N 个皇后，然后使得任意两个皇后不能相互攻击，没有玩的国际象棋，皇后的攻击范围是整个一行一列以及对角线攻击，以 N=8 为例，问题就是摆放 8 个皇后，皇后之间不能相互攻击。先看一个最关键的特性，因为每个皇后会攻击一行或一列，一个最基本的要求是每行只有一个皇后，每列也只有一个皇后，每条对角线也只有一个皇后，这道题是用递归进行搜索，根据这个特性可以减去不需要的判断。

皇后的攻击范围是行、列、对角线，如上图，棋盘是 11 是有 1 个解棋盘是 22 与 33 是无解，8 皇后是 92 个解，棋盘是对称的，fundamental 是基本解，上下对称、左右对称、对角线对称。解的增长是很快的，当棋盘是 2424 时解基本上就是天文数字了，题目给出 N 的范围是 1-9 每一行只能放一个皇后，用递归的方法，当前行找一个位置放皇后，下一行再找一个位置放皇后，每放置一个皇后将它所有的攻击范围标记成不能走，下一行皇后放置的位置范围就少了，这就是递归的过程。

它的对角线的特点，8 皇后，正对角线和反对角线分别有 15 条，对应的公式为 2*n-1。放置一个皇后后可以将当前位置的对角线设置为不可走，但是这样会浪费很多时间和空间，其实我们可以用一个变量来描述这一行、一列、一个对角线。最小单位就是一行、一列、一个对角线，对角线从左上角到右下角标记成 0...14，我们就可以用这 15 个变量来描述这 15 条对角线，对角线的索引和格子的 xy 有什么关系呢？红色对角线的索引 idx = x + y，蓝色对角线的索引 idx = x - y + (n - 1)，这样在递归搜索的时候就可以减少判断了。看伪代码，按行来搜索，所以就不用来记录第几行直接用 y 来表示。因为不能放到之前的行数中去，比如递归到第 4 行的时候，前面 3 行已经放置了 3 个皇后，现在要在第 4 行中找一个合适的位置放置第 4 行的皇后，所以行数就不用数组来描述它是否已经被占据了，从 0 到 y-1 的行数已经被占据了，是不能放置皇后的。当 y == n 的时候，表示超过棋盘了，即已经放置了 n 个皇后了，找到解了，即把当前的棋盘追加到返回结果中，返回，递归结束。对于第 y 行来说，要循环这个列，x 从 0 到 n 开始循环，先判断当前格式是否能走，能走的话将皇后放置在这个位置并继续下一层递归，递归完之后要将这一行清空，表示这一行没有皇后，并将这行的位置置为可走。available 判断是否可走的实现：判断列是否可走，正对角线是否可走，反对角线是否可走。

三、解题方法

3.1 Java 实现

public class Solution {    public List<List<String>> solveNQueens(int n) {        board = new ArrayList<>();        for (int i = 0; i < n; i++) {            // jdk11            // board.add(".".repeat(n));            board.add(".".repeat(n).toCharArray());        }        cols = new boolean[n];        diag1 = new boolean[2 * n - 1];        diag2 = new boolean[2 * n - 1];        sols = new ArrayList<>();
        nqueens(n, 0);
        return sols;    }
    /**     * 记录棋盘     */    private List<char[]> board;    /**     * 记录第x列是否有皇后     */    private boolean[] cols;    /**     * 记录第x条正对角线上是否有皇后     */    private boolean[] diag1;    /**     * 记录第x条反对角线上是否有皇后     */    private boolean[] diag2;    /**     * 记录解     */    private List<List<String>> sols;
    boolean available(int x, int y, int n) {        return !cols[x] && !diag1[x + y] && !diag2[x - y + n - 1];    }
    /**     * 更新棋盘     *     * @param x     * @param y     * @param n     * @param put     */    void updateBoard(int x, int y, int n, boolean put) {        cols[x] = put;        diag1[x + y] = put;        diag2[x - y + n - 1] = put;        board.get(y)[x] = put ? 'Q' : '.';    }
    void nqueens(int n, int y) {        if (y == n) {            List<String> tmp =  board.stream().map(t -> String.valueOf(t)).collect(Collectors.toList());            sols.add(tmp);            return;        }        for (int x = 0; x < n; x++) {            if (!available(x, y, n)) {                continue;            }            // 更新棋盘            updateBoard(x, y, n, true);            nqueens(n, y + 1);            // 将棋盘还原            updateBoard(x, y, n, false);        }    }}

复制代码

四、总结小记

2022/6/6 回溯+递归来解决八皇后问题

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/57d787dd7bfdb8422e6df7ed6】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景