N皇后问题

路九阳大约 2 分钟教学文档回溯与分支限界-dfs

N皇后问题

题目描述

解题思路（回溯法 Backtracking）

n 皇后问题要求在 n × n 棋盘 上放置 n 个皇后，使得：

任何两个皇后不能在 同一行
不能在 同一列
不能在 同一斜线（两种斜线）

🌟 关键观察：

我们将 一行一行放置皇后。

行号固定后，只需决定皇后放在哪一列。
我们需要记录哪些列/斜线已被占用。

如何判断斜线？

对于位置 (row, col)：

斜线类型	数学特性	用来判定冲突
主对角线（↘，从左上到右下）	row - col = 常数	用一个集合记录：`diag1`
副对角线（↙，从右上到左下）	row + col = 常数	用一个集合记录：`diag2`

所以只要 列、主对角线、副对角线 之一冲突，就不能放皇后。

🌟 回溯算法的结构：

def backtrack(row):
    如果 row == n：
        找到一个完整解，加入答案
        return

    对列 col 从 0 到 n-1:
        如果该列和斜线都安全:
            放皇后
            进入下一行 backtrack(row + 1)
            撤销皇后（回溯）

Python 代码

def solveNQueens(n):
    results = []
    board = ["." * n for _ in range(n)]

    cols = set()      # 已占用的列
    diag1 = set()     # 主对角线 row - col
    diag2 = set()     # 副对角线 row + col

    def backtrack(row):
        if row == n:
            results.append(board.copy())
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            # 放置皇后
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            board[row] = board[row][:col] + "Q" + board[row][col+1:]

            # 下一行
            backtrack(row + 1)

            # 回溯（撤销）
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

            board[row] = board[row][:col] + "." + board[row][col+1:]

    backtrack(0)
    return results


# 测试
print(solveNQueens(4))

示例输出（n=4）

[
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

时间复杂度

最坏时间复杂度：O(n!)
空间复杂度：O(n)

这是标准的 n 皇后回溯算法，效率高、实现简洁。