题目难度: 困难
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:
- 输入：4
- 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
- 解释: 4 皇后问题存在如下两个不同的解法。
[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
题目思考
- 如何利用已经计算出的结果?
解决方案
思路
- 分析题目, 有效的摆放需要满足四个条件:
- 任意两个皇后都不在同一行;
- 任意两个皇后都不在同一列;
- 任意两个皇后都不在同一正向对角线上 (例如(0,1)和(1,2)是在同一正对角线);
- 任意两个皇后都不在同一反向对角线上 (例如(0,1)和(1,0)是在同一反对角线);
- 我们可以逐行统计, 每一行保证只放置一个皇后, 这样自动满足第一个条件; 而对于剩下 3 个条件, 我们可以使用三个集合, 记录当前已经使用的列/正对角线/反对角线
- 其中列集合直接存储列号即可; 而对于正对角线/反对角线集合, 通过观察我们可以发现: 假设有两个坐标(r1,c1)和(r2,c2), 当
r1-c1==r2-c2时, 它们在同一正对角线上, 而当r1+c1==r2+c2时, 它们在同一反对角线上, 也即正对角线集合存储r-c, 反对角线集合存储r+c - 搞定了需要的数据结构, 接下来就是具体实现了, 这里用的是典型的递归回溯思路:
- 对于每一行 r, 我们都遍历所有列 c, 检查当前坐标(r,c)是否在上述三个集合中
- 该坐标同时不在三个集合的话, 说明满足所有条件, 可以把皇后放在这里
- 然后追加该行字符串, 并更新相应集合, 继续递归调用, 处理下一行
- 下面的代码中有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N!): 第一行有 N 种选择, 第二行有 N-1 种选择, 依此类推, 共需考虑N!种情况 - 空间复杂度
O(N): 无论是递归栈, 还是三个集合, 最多都只有 N 个元素
代码
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 回溯+三集合
res = []
# 使用三个集合分别记录当前用过的列/对角线/反对角线
def solve(r, board, cols, diags, rdiags):
if r == n:
# 遍历完所有行了, 找到一个有效解, 将其加入最终结果中
res.append(board)
return
for c in range(n):
# 注意对角线是记录r-c, 反对角线是记录r+c!!!!
if c not in cols and r - c not in diags and r + c not in rdiags:
# 当前点满足不和已有点在同一列/对角线/反对角线上, 可以将皇后放在这里
# 追加该行字符串并更新相应集合, 继续递归调用
solve(r + 1, board + ["." * c + "Q" + "." * (n - c - 1)], cols | {c}, diags | {r - c}, rdiags | {r + c})
solve(0, [], set(), set(), set())
return res 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号