关于leetcode:leetcode-51-NQueens-N-皇后困难

5次阅读

共计 2395 个字符，预计需要花费 6 分钟才能阅读完成。

标签: 搜寻

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 个皇后，皇后之间不能互相攻打。先看一个最要害的个性，因为每个皇后会攻打一行或一列，一个最根本的要求是每行只有一个皇后，每列也只有一个皇后，每条对角线也只有一个皇后，这道题是用递归进行搜寻，依据这个个性能够减去不须要的判断。

皇后的攻打范畴是行、列、对角线，如上图，棋盘是 1 1 是有 1 个解棋盘是 2 2 与 3 3 是无解，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 判断是否可走的实现：判断列是否可走，正对角线是否可走，反对角线是否可走。

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);
        }
    }
}