[51][困难][回溯] N皇后

题目描述

51. N 皇后 52. N皇后 II

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的棋盘, 它的对角线和反对角线各有2n - 1条, 其中:

• 同一条对角线位置的横纵坐标相减恒定, 即i-j不变

• 反对角线的横纵坐标之和恒定, 即i+j不变

这样我们就可以创建4个数组, 分别记录每行, 每列, 每条对角线和反对角线是否已经被占用.

遍历时从某个坐标出发, 向四周搜索, 是最简单的搜索方法. 但这种方法复杂度高, 最坏的情况下, 每个皇后都要遍历所有棋盘位置才能确定. 提交后超时.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n == 1:
            return [['Q']]

        board = [['.'] * n for _ in range(n)]
        row = [False] * n
        col = [False] * n
        diagonal = {i: False for i in range(-(n - 1), n)}
        back_diagonal = {i: False for i in range((n - 1) * 2 + 1)}
        seen = [[False] * n for _ in range(n)]
        res = set()

        def dfs(i, j, count):
            if count == n:
                res.add('|'.join([''.join(t) for t in board]))
                return

            seen[i][j] = True
            if not row[i] and not col[j] and not diagonal[i - j] and not back_diagonal[i + j]:
                row[i] = col[j] = diagonal[i - j] = back_diagonal[i + j] = True
                board[i][j] = 'Q'
                if 0 <= i - 1 < n and not seen[i - 1][j]:
                    dfs(i - 1, j, count + 1)
                if 0 <= i + 1 < n and not seen[i + 1][j]:
                    dfs(i + 1, j, count + 1)
                if 0 <= j - 1 < n and not seen[i][j - 1]:
                    dfs(i, j - 1, count + 1)
                if 0 <= j + 1 < n and not seen[i][j + 1]:
                    dfs(i, j + 1, count + 1)
                board[i][j] = '.'
                row[i] = col[j] = diagonal[i - j] = back_diagonal[i + j] = False

            if 0 <= i - 1 < n and not seen[i - 1][j]:
                dfs(i - 1, j, count)
            if 0 <= i + 1 < n and not seen[i + 1][j]:
                dfs(i + 1, j, count)
            if 0 <= j - 1 < n and not seen[i][j - 1]:
                dfs(i, j - 1, count)
            if 0 <= j + 1 < n and not seen[i][j + 1]:
                dfs(i, j + 1, count)

            seen[i][j] = False

        dfs(0, 0, 0)
        return [t.split('|') for t in res]

而我们知道, 每行有且只能有一个皇后, 因此可以按行探索, 每行内搜索所有可能摆放皇后的位置, 遍历完毕后, 探索下一行, 直到所有行探索完毕, 也就得到了所有可能的结果. 因此我们不再需要记录每一行是否被占用了, 而是记录每一行对应的皇后棋子摆放列的索引.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:    
        row = [-1] * n
        col = [False] * n
        diagonal = {i: False for i in range(-(n - 1), n)}
        back_diagonal = {i: False for i in range((n - 1) * 2 + 1)}
        res = []

        def dfs(i):
            if i == n:
                t_res = []
                for k in range(n):
                    tmp = ['.'] * n
                    tmp[row[k]] = 'Q'
                    t_res.append(''.join(tmp))
                res.append(t_res)
                return

            for j in range(n):
                if col[j] or diagonal[i - j] or back_diagonal[i + j]:
                    continue
                row[i] = j
                col[j] = diagonal[i - j] = back_diagonal[i + j] = True
                dfs(i + 1)
                col[j] = diagonal[i - j] = back_diagonal[i + j] = False

        dfs(0)
        return res

参考资料

• N皇后