博客

详解N皇后问题原理与使用方法

N皇后问题

作用

N皇后问题是经典的回溯算法问题，用于解决在N x N的棋盘上放置N个皇后问题。N皇后问题有多解，即对于任意满足N > 3的正整数N，N皇后问题都有解。

N皇后问题与其他回溯算法问题类似，是为了求出所有的解，而非一种满足条件即可的问题。因此，N皇后问题的解法需要遍历所有的可能性，只有当问题满足条件时才会将解保存并继续向下搜索，否则回退到上一层继续寻找其他可能解。

N皇后问题常常被用于评价算法的效率和复杂度，因此熟练掌握N皇后问题的解法对于程序员来说是非常重要的。

使用方法

N皇后问题的解法基本上可以分为两类，一类是通过深度优先搜索完成，另一类则是通过分治法和位运算完成。

深度优先搜索

对于深度优先搜索，我们可以使用回溯法解决N皇后问题。具体步骤如下：

  1. 从棋盘的第一行开始，以列为单位一列一列地搜索（可以简化为从每行开始搜索，因为任选一行开始搜索，有置换对称性）。定义一个列表记录当前所有已放置皇后所在的列号。

  2. 在当前行从第一列开始搜索，对于每一列，判断该列是否合法，即在当前列放置皇后是否会受到当前所有已放置皇后的攻击。如果不合法，直接跳过本次循环，进入下一次循环；如果合法，将该列号添加到已放置皇后的列表中，并进入下一行搜索。

  3. 重复2，直到搜索完最后一行。此时所有皇后已经放置在棋盘上，保存这个解，并回退到上一层。然后尝试在当前行的下一列寻找新的解。

  4. 重复2、3直到搜索完所有的可能性。

下面是python代码示例：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.result = []
        self.cols = set()
        self.pie = set()
        self.na = set()
        self.dfs([], 0, n)
        return self._generate_result(n)

    def dfs(self, cur_state, row, n):
        if row == n:
            self.result.append(cur_state)
            return
        for col in range(n):
            if col in self.cols or row + col in self.pie or row - col in self.na:
                continue
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)
            self.dfs(cur_state + [col], row + 1, n)
            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

    def _generate_result(self, n):
        board = []
        for res in self.result:
            for i in res:
                board.append('.' * i + 'Q' + '.' * (n - i - 1))
        return [board[i: i + n] for i in range(0, len(board), n)]

分治法和位运算

下面是通过分治法和位运算完成N皇后问题的示例。

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1:
            return 0

        self.count = 0
        self.dfs(n, 0, 0, 0, 0)
        return self.count

    def dfs(self, n, row, cols, pie, na):
        if row == n:
            self.count += 1
            return

        bits = (~(cols | pie | na)) & ((1 << n) - 1)
        while bits:
            p = bits & -bits
            bits = bits & (bits - 1)
            self.dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)

示例说明

示例一：深度优先搜索

假设我们要在8×8的棋盘上放置8个皇后，并要求皇后之间不能互相攻击。下面是程序的运行结果：

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

示例二：分治法和位运算

假设我们要求解4皇后问题。下面是程序的运行结果：

2

总结

N皇后问题是经典的回溯算法问题，解决方法有深度优先搜索和分治法和位运算两种。熟练掌握N皇后问题的解法对于程序员来说是非常重要的。

Tags: