Solutions CS101

Appearance

51.N皇后 ​

backtracking, https://leetcode.cn/problems/n-queens/

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例 1：

img
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9

思路：模仿8皇后的写法

python
# 曾孜博 24工学院
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        p = []  # 存放所有解
        def dfs(r):  # 当前放置到第 len(r) 行
            if len(r) == n:  # 已放满
                p.append(['.'*(t-1)+'Q'+'.'*(n-t) for t in r])
                return
            for i in range(1, n+1):  # 枚举列号（1~n）
                if i in r: continue  # 同列冲突
                for j in range(len(r)):  # 检查对角线冲突
                    if abs(i - r[j]) == abs(len(r) - j):  
                        # 列差 == 行差，说明在对角线上
                        break
                else:  # 没冲突
                    r.append(i)
                    dfs(r)
                    r.pop()  # 回溯
        dfs([])
        return p

逻辑解析

  • r 是一个列表，r[k] = t 表示第 k 行的皇后放在第 t 列。
  • 同一列冲突：if i in r
  • 对角线冲突：abs(i - r[j]) == abs(len(r) - j)
    • “行差 = 列差” ⇒ 在同一对角线。
  • 每次递归进入下一行，直到放满 n 个皇后。
  • 转换输出格式：'.'*(t-1)+'Q'+'.'*(n-t) 把列号变成字符串形式。

示例

当 n=4 时：

r = [2, 4, 1, 3]  → ".Q.."、"...Q"、"Q..."、"..Q."
python
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        solutions = []
        def queens(row: int, cols: List[int], ldiags: Set[int], rdiags: Set[int]) -> None:
            if row == n:
                solutions.append(["".join("Q" if j == cols[i] else "." for j in range(n)) for i in range(n)])
                return
            for j in range(n):
                if j not in cols and row + j not in ldiags and row - j not in rdiags:
                    queens(row + 1, cols + [j], ldiags | {row + j}, rdiags | {row - j})

        queens(0, [], set(), set())
        return solutions

斜率是+1或者-1，截距是常数。遍历每一列 q，检查当前列 q 是否可以放置皇后：

  • q not in queens 确保没有其他皇后在同一列。
  • p - q not in xy_diff 确保没有其他皇后在同一左下到右上的对角线。
  • p + q not in xy_sum 确保没有其他皇后在同一左上到右下的对角线。
python
from typing import List
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def dfs(queens, xy_diff, xy_sum):
            p = len(queens)
            if p == n:
                result.append(queens)
                return
            for q in range(n):
                if q not in queens and p - q not in xy_diff and p + q not in xy_sum:
                    dfs(queens + [q], xy_diff + [p - q], xy_sum + [p + q])
        result = []
        dfs([], [], [])
        print(result)
        return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]

if __name__ == '__main__':
    s = Solution()
    print(s.solveNQueens(4))