题目0051:N皇后

题目描述

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

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

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

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

示例:

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释: 4皇后问题存在两个不同的解法。

提示:皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一到七步,可进可退。

解题技巧

• 回溯法

第一个想法是使用蛮力法,意味着生成在棋盘上放置N个皇后的所有可能的情况,并且检查是否保证没有皇后可以互相攻击。这意味着$\mathcal{O}(N^N)$的时间复杂度,因此我们必须考虑优化。

下面是两个有用的编程概念。

第一个叫做约束编程.

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

第二个叫做回溯法.

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

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

一行只可能有一个皇后且一列也只可能有一个皇后:这意味着没有必要再棋盘上考虑所有的方格,只需要按列循环即可。

对于所有的主对角线有行号+列号=常数,对于所有的次对角线有`行号-列号=常数:这可以让我们标记已经在攻击范围下的对角线并且检查一个方格(行号,,列号))是否处在攻击位置。

现在已经可以写回溯函数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: int) -> List[List[str]]:
        def could_place(row, col):
            return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])

        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = 1
            hill_diagonals[row - col] = 1
            dale_diagonals[row + col] = 1

        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            hill_diagonals[row - col] = 0
            dale_diagonals[row + col] = 0

        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)

        def backtrack(row = 0):
            for col in range(n):
                if could_place(row, col):
                    place_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    remove_queen(row, col)

        cols = [0] * n
        hill_diagonals = [0] * (2 * n - 1)
        dale_diagonals = [0] * (2 * n - 1)
        queens = set()
        output = []
        backtrack()
        return output

复杂度分析

时间复杂度:$\mathcal{O}(N!)$. 放置第1个皇后有N种可能的方法,放置两个皇后的方法不超过N(N - 2),放置3个皇后的方法不超过N(N - 2)(N - 4),以此类推。总体上,时间复杂度为$\mathcal{O}(N!)$.

空间复杂度:$\mathcal{O}(N)$. 需要保存对角线和行的信息。