leetcode51.N皇后

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

上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

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

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

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自百度百科 - 皇后）

约束编程

基本含义是在放置每个皇后以后增加限制。当在棋盘上放置了一个皇后时，立即排除当前行，列和对应的两个对角线。该过程传递了约束从而有助于减少需要考虑情况数。

第二种方法叫做回溯法

当在棋盘上放置了几个皇后且不会相互攻击。但是选择的方案不是最优的，因为无法放置下一个皇后。此时我们该怎么做？回溯。意思就是回退一步，来改变最后放置皇后的位置并且接着往下放置。如果还是不行，再回溯。

方法1：回溯

在建立算法之前，我们来考虑两个有用的细节。

一行只可能有一个皇后且一列也只可能有一个皇后。

这意味着没有必要在棋盘上考虑所有的方格。只需要按列循环即可。

对于所有的主对角线(蓝线)有行号-列号=常数（一条线上是同一个常数），对于所有的次对角线(红线)有行号+列号=常数（一条线上是同一个常数）。

这可以让我们标记已经在攻击范围下的对角线并且检查一个方格(行号，列号)是否处于攻击位置。

回溯函数backtrack(row=0)。

从第一个row=0开始。
循环列并且试图在每个column中放置皇后。
- 如果方格(row, column)不在攻击范围内
  - 在(row, column)方格上放置皇后。
  - 排除对应行，列和两个对角线的位置
  - if 所有的行被考虑过，row == N
    - 意味着我们找到了一个解
  - Else
    - 继续考虑接下来的皇后放置backtrack(row + 1)。
  - 回溯：将在(row, column)方格的皇后移除。

代码

class Solution:
    def solveNQueens(self, n):
        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            print('remove', row - col + n - 1)
            hile_diagonal[row - col + n - 1] = 0
            dale_diagonal[row + col] = 0
        
        def could_place(row, col):
            return not (cols[col] + hile_diagonal[row - col + n - 1] + dale_diagonal[row + col])
        
        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = 1
            print('hile', row - col + n - 1)
            print('dale', row + col)
            hile_diagonal[row - col + n - 1] = 1
            dale_diagonal[row + col] = 1
    
        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + (n-1-col) * '.' )
            output.append(solution)

        def backtrack(row):
            for col in range(n):
                if could_place(row, col):
                    place_queen(row, col)
                    if row == n - 1:
                        add_solution()
                    else:
                        backtrack(row+1)
                    remove_queen(row, col)
        output = []
        cols = [0] * n
        hile_diagonal = [0] * (2 * n - 1)
        dale_diagonal = [0] * (2 * n - 1)
        queens = set()
        backtrack(row=0)
        return output

也可以用之前的回溯板子：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row):
            if row == n:
                output.append(['.' * col + 'Q' + '.' * (n - 1 - col) for col in queens])
                return
            for col in range(n):
                if cols[col] and hill_diagonal[row - col + n - 1] and dale_diagonal[row + col]:
                    queens.append(col)
                    cols[col] = 0
                    hill_diagonal[row - col + n - 1] = 0
                    dale_diagonal[row + col] = 0
                    backtrack(row + 1)
                    cols[col] = 1
                    hill_diagonal[row - col + n - 1] = 1
                    dale_diagonal[row + col] = 1
                    queens.pop()
        output = []
        queens = []
        cols = [1] * n
        hill_diagonal = [1] * (2 * n - 1)
        dale_diagonal = [1] * (2 * n - 1)
        backtrack(row = 0)
        return output

道理是一样的，时间更快了~

复杂度分析

时间复杂度：$\mathcal{O}(N!)$. 放置第 1 个皇后有 $N$ 种可能的方法，放置两个皇后的方法不超过 $N(N - 2)$，放置 3 个皇后的方法不超过 $N(N - 2)(N - 4) $，以此类推。总体上，时间复杂度为 $\mathcal{O}(N!)$ .
空间复杂度：$\mathcal{O}(N)$ . 需要保存对角线和行的信息。

参考资料

官方题解