Leetcode: 【每日一题】- 2020-01-09 - 51. N皇后

[azl397985856]

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

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[azl397985856]

超级简单的套模板回溯法（Python）

如果采取完全暴力，时间复杂度是N^N肯定是不能通过的。

符合直觉的想法是剪枝， 比如选取了第一行，我们直接排除横竖斜三条线，然后继续选择。 关于如何排除，我们可以使用hashmap记录三个方向即可。 当不满足题意的时候，我们继续从头开始。

实际上回溯法和这个做法类似，只是每次不是从头，而是回退一步，继续尝试，不行的话继续回退一步。。。

以下是我经常使用解题模板，很多题目我都在用

Code

#
# @lc app=leetcode.cn id=51 lang=python3
#
# [51] N皇后
#

# @lc code=start


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        empty = [['.'] * n for _ in range(n)]
        row = set()
        col = set()
        ldiagonal = set()
        rdiagonal = set()

        def backtrack(result, temp, i, j, cnt):
            if cnt == n:
                return result.append([''.join(row) for row in temp])
            for ii in range(i, n):
                for jj in range(j, n):
                    if jj in col or ii + jj in ldiagonal or ii - jj in rdiagonal:
                        continue
                    temp[ii][jj] = 'Q'
                    row.add(ii)
                    col.add(jj)
                    ldiagonal.add(ii + jj)
                    rdiagonal.add(ii - jj)
                    backtrack(result, temp, ii + 1, 0, cnt + 1)
                    row.remove(ii)
                    col.remove(jj)
                    ldiagonal.remove(ii + jj)
                    rdiagonal.remove(ii - jj)
                    temp[ii][jj] = '.'

        backtrack(res, empty, 0, 0, 0)

        return res

# @lc code=end

[unclegem]

Java题解 简单明了

首先我们判断位置是否可行的，也就是不在同一行，不在同一列，且不在对角线上。
因为pos集合记录的是每一行皇后放的位置，所以我们无需判断是否在一行，只需判断其他两个条件是否满足。接着一行一行的找，遇到满足条件的列就把位置加进去加进去，当pos集合的大小等于n的时候，就说明满足条件，可以把结果打印。

public List<List<String>> solveNQueens(int n) {

    List<List<String>> res = new ArrayList<>();
    List<Integer> colIndex = new ArrayList<>();
    dfs(res, colIndex, n);
    return res;
}

public void dfs(List<List<String>> res, List<Integer> pos,  int max) {

    if (pos.size() == max) {
        res.add(print(pos));
        return;
    }
    for (int colPos = 0; colPos < max; colPos++) {
        if (!isValid(pos, colPos))
            continue;
        pos.add(colPos);
        dfs(res, pos, max);
        pos.remove(pos.size() - 1);
    }
}

public List<String> print(List<Integer> pos) {

    List<String> res = new ArrayList<>();
    for (int row = 0; row < pos.size(); row++) {
        StringBuilder sb = new StringBuilder();
        for (int col = 0; col < pos.size(); col++)
            sb.append(pos.get(row) != col ? '.' : 'Q');
        res.add(sb.toString());
    }
    return res;
}

public boolean isValid(List<Integer> pos, int col) {


    int row = pos.size(); //已经存了多少行
    for (int rowPos = 0; rowPos < row; rowPos++) {
        //不能在同一列或者对角线
        if (pos.get(rowPos) == col || Math.abs(rowPos - row) == Math.abs(pos.get(rowPos) - col))
            return false;
    }
    return true;
}

[azl397985856]

@unclegem 突然发现你是我交换友链的竞赛大佬！

[unclegem]

@unclegem 突然发现你是我交换友链的竞赛大佬！

😂宝石叔叔=unclegem
😂大佬算不上

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.