LeetCode 51. N 皇后

题目描述
在一个 N×N 的棋盘上放置 N 个皇后，要求它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。给定整数 N，返回所有不同的解决方案（用棋盘布局表示）。

解题过程

1. 问题分析

• 关键约束：
  1. 每行只能放一个皇后（因为 N 个皇后放在 N 行，每行必有一个）。
  2. 每列只能放一个皇后。
  3. 每条对角线（主对角线和副对角线）上最多一个皇后。
• 搜索目标：找到所有满足条件的棋盘布局，用 Q 表示皇后，. 表示空位。

2. 回溯算法框架

• 按行逐行放置皇后，避免行冲突。
• 在每一行中，尝试所有列位置，检查当前列和两条对角线是否已被占用。
• 若合法则放置，并递归下一行；若不合法则回溯。

3. 关键细节

（1）如何表示棋盘？

• 使用二维列表 board，初始为全 .。
• 或使用一维列表 queens：queens[i] = j 表示第 i 行的皇后在第 j 列。

（2）如何检查对角线冲突？

• 主对角线（左上到右下）：行号 - 列号 = 常数（范围 [-(N-1), N-1]）。
• 副对角线（右上到左下）：行号 + 列号 = 常数（范围 [0, 2N-2]）。
• 可用三个集合记录已占用的列、主对角线、副对角线：
  • cols：已使用的列索引。
  • diag1：已使用的主对角线常数（row - col）。
  • diag2：已使用的副对角线常数（row + col）。

4. 算法步骤

1. 初始化空棋盘和三个空集合 cols, diag1, diag2。
2. 定义回溯函数 backtrack(row)：
   • 若 row == N：说明所有行已放置完毕，将当前棋盘加入结果列表。
   • 否则，遍历当前行的每一列 col：
     • 计算 d1 = row - col, d2 = row + col。
     • 若 col 不在 cols 中，且 d1 不在 diag1 中，且 d2 不在 diag2 中：
       • 放置皇后：记录 col, d1, d2 到集合，更新棋盘。
       • 递归 backtrack(row + 1)。
       • 回溯：从集合中移除 col, d1, d2，恢复棋盘。
3. 从第 0 行开始调用 backtrack(0)。
4. 将结果中的棋盘格式化为题目要求的字符串列表。

5. 举例说明（N=4）

步骤演示：

• 初始：row=0，尝试 col=0（合法），记录列 0、对角线 -0 和 0。
• 递归到 row=1：
  • col=0（列冲突），col=1（对角线冲突：d1=0, d2=2 均未出现，但检查主对角线 1-1=0 已在集合？不对，此处应重新计算：row=1, col=1 → d1=0 已存在！冲突）。
  • col=2 合法，继续递归。
• 最终找到解：[1, 3, 0, 2] 对应棋盘：

.Q..
...Q
Q...
..Q.

6. 复杂度分析

• 时间复杂度：最坏 O(N!)，因为每行选择减少（但受对角线约束剪枝）。
• 空间复杂度：O(N)（递归栈和集合存储）。

7. 代码实现（Python）

def solveNQueens(N):
    def backtrack(row):
        if row == N:
            res.append(["".join(row) for row in board])
            return
        for col in range(N):
            d1, d2 = row - col, row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue
            # 放置皇后
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)
            board[row][col] = 'Q'
            backtrack(row + 1)
            # 回溯
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)
    
    res = []
    board = [['.'] * N for _ in range(N)]
    cols, diag1, diag2 = set(), set(), set()
    backtrack(0)
    return res